Missing Number #

Problem Statement #

Given an array containing n distinct numbers taken from the range 0, 1, 2, ..., n, find the one number that is missing from the array.

Examples #

Example 1:

• Input: [3,0,1]
• Output: 2
• Explanation: The array contains numbers from 0 to 3, but 2 is missing.

Example 2:

• Input: [9,6,4,2,3,5,7,0,1]
• Output: 8
• Explanation: The array should contain numbers from 0 to 9, but 8 is missing.

Solution #

var missingNumber = function(nums) {
  // Calculate sum of all elements in the array
  let sum = 0;
  
  // Iterate through array and accumulate sum
  for (let i = 0; i < nums.length; i++) {
    sum += nums[i];
  }
  
  // Calculate expected sum using Gauss's formula
  let target = ((nums.length) * (nums.length + 1)) / 2;
  
  // The difference is our missing number
  return target - sum;
};

Approach #

The solution uses a mathematical approach based on the sum of consecutive integers. Instead of searching through the array multiple times or using additional data structures, we leverage the fact that we know exactly what numbers should be present and can calculate what their sum should be.

The key insight is that if we know the expected sum of all numbers from 0 to n, and we know the actual sum of the numbers present in the array, the difference between these two values must be the missing number.

Algorithm Breakdown #

Step 1: Calculate Actual Sum #

for (let i = 0; i < nums.length; i++) {
  sum += nums[i];
}

This loop iterates through each element in the input array and accumulates their sum. After this loop completes, sum contains the total of all elements currently present in the array.

For example, with input [3,0,1]:

• Initially: sum = 0
• After processing 3: sum = 3
• After processing 0: sum = 3
• After processing 1: sum = 4

Step 2: Calculate Expected Sum #

let target = ((nums.length) * (nums.length + 1)) / 2;

This line uses Gauss’s formula for the sum of consecutive integers. Let me explain the mathematics behind this:

Gauss’s Formula: The sum of consecutive integers from 1 to n is: n × (n + 1) / 2

However, our sequence starts from 0, not 1. Since 0 doesn’t contribute to the sum, we can think of this as summing n+1 numbers where the first is zero.

Here’s why we use nums.length instead of nums.length + 1:

• The array has nums.length elements
• But we’re missing one number, so the complete sequence should have nums.length + 1 elements (from 0 to n)
• When we apply the formula for n+1 elements: (n+1) × ((n+1) + 1) / 2
• Simplifying: (n+1) × (n+2) / 2
• But since our sequence starts at 0, we can substitute n with nums.length to get: nums.length × (nums.length + 1) / 2

For example, with input [3,0,1]:

• nums.length = 3
• Complete sequence should be: [0,1,2,3] (4 elements)
• Expected sum: 3 × 4 / 2 = 6

Step 3: Find Missing Number #

return target - sum;

The missing number is simply the difference between what the sum should be and what it actually is.

Continuing our example:

• target = 6 (sum of 0,1,2,3)
• sum = 4 (sum of 0,1,3)
• missing = 6 - 4 = 2

Complexity Analysis #

Time Complexity: O(n)

• We iterate through the array once to calculate the sum
• All other operations are O(1)

Space Complexity: O(1)

• We only use a constant amount of extra space for variables sum and target
• No additional data structures are needed

Alternative Approaches #

While the mathematical approach is elegant and efficient, there are other ways to solve this problem:

1. XOR Approach #

Using the XOR bitwise operator, which has the property that a ^ a = 0 and a ^ 0 = a:

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

2. Hash Set Approach #

Create a set of all numbers and check which one is missing:

var missingNumber = function(nums) {
  const numSet = new Set(nums);
  for (let i = 0; i <= nums.length; i++) {
    if (!numSet.has(i)) {
      return i;
    }
  }
};

3. Sorting Approach #

Sort the array and find the gap:

var missingNumber = function(nums) {
  nums.sort((a, b) => a - b);
  for (let i = 0; i < nums.length; i++) {
    if (nums[i] !== i) {
      return i;
    }
  }
  return nums.length;
};

Why Choose the Sum Approach? #

The mathematical sum approach presented in the main solution is optimal because:

1. Simplicity: The logic is straightforward and easy to understand once you know Gauss’s formula
2. Efficiency: O(n) time complexity with only one pass through the array
3. Space-efficient: O(1) space complexity with no additional data structures
4. No edge cases: Works for all valid inputs without special handling

This makes it an excellent solution for technical interviews and real-world applications where performance matters.