Finding the Missing Number in a Sequence

The "Missing Number" problem is a classic example of array and bit manipulation in computer science. It involves finding a missing number in a sequence.

Problem Statement

Given an array containing n distinct numbers taken from 0 to n, find the one number that is missing from the sequence.

Examples

• Input: nums = [3,0,1] Output: 2 Explanation: Numbers 0, 1, and 3 are present. The missing number is 2.

• Input: nums = [0,1] Output: 2 Explanation: Numbers 0 and 1 are present. The missing number is 2.

Solutions

Mathematical Solution:

function missingNumber(nums) {
  let expectedSum = (nums.length * (nums.length + 1)) / 2;
  let actualSum = nums.reduce((a, b) => a + b, 0);
  return expectedSum - actualSum;
}

Bit Manipulation Solution:

function missingNumber(nums) {
  let xor = 0;
  for (let i = 0; i < nums.length; i++) {
    xor ^= i ^ nums[i];
  }
  return xor ^ nums.length;
}

Breaking Down the Solutions

• Mathematical Approach:
  • The sum of the first n numbers is n * (n + 1) / 2. We can use this formula to find the expected sum of the numbers in the array.
  • We can then find the actual sum of the numbers in the array by using the reduce method.
  • The difference between the expected sum and the actual sum is the missing number.
• Bit Manipulation Approach:
  • We can use the XOR operator to find the missing number.
  • The XOR operator is a bitwise operator that returns a 1 if the bits are different and a 0 if the bits are the same.
  • We can use the XOR operator to find the missing number by XORing the index of each number in the array with the number itself.
  • The XOR operator is associative and commutative, so we can XOR the numbers in any order.
  • We can XOR the index of each number in the array with the number itself to find the missing number.

Conclusion

The "Missing Number" problem is a classic example of array and bit manipulation in computer science. It involves finding a missing number in a sequence. We can solve this problem using mathematical and bit manipulation techniques.