08. Find the Missing Number in an Array

Difficulty:EasyPattern:Math / Bit ManipulationTime:O(n)Space:O(1)

Given an array nums containing $n$ distinct numbers in the range $[0, n]$, return the only number in the range that is missing from the array.

How It Works & Algorithmic Design

This problem can be solved mathematically using Gauss's Summation Formula or bit manipulation with XOR:

Mathematical Sum Method:
- The sum of integers from $0$ to $n$ is calculated using the formula $S_n = \frac{n \cdot (n + 1)}{2}$.
- Calculate the actual sum of elements in nums.
- The missing number is simply $S_n - \text{actualSum}$.
Bit Manipulation (XOR Method):
- XORing a number with itself yields zero ($a \oplus a = 0$).
- XOR all indices from $0$ to $n$ together with all values in nums. Duplicate numbers cancel out, leaving only the missing number.

Why This Approach Works Best

Both methods run in $O(n)$ time complexity and $O(1)$ space without requiring array sorting ($O(n \log n)$) or extra hash sets ($O(n)$ space).

Example Walkthrough

Input: [3, 0, 1] (n = 3)

Expected range [0, 1, 2, 3].

Expected Sum Formula: (3 * 4) / 2 = 6

Sum of numbers from 0 to 3.

Actual Sum: 3 + 0 + 1 = 4

Sum of given input array.

Output: 6 - 4 = 2

The missing number is 2.

Answer: Find missing number using Gauss's Sum

function missingNumber(nums) {
  const n = nums.length;
  const expectedSum = (n * (n + 1)) / 2;
  const actualSum = nums.reduce((acc, val) => acc + val, 0);
  return expectedSum - actualSum;
}

💡 Subtract the array sum from the expected arithmetic progression total.

Key Takeaways

Gauss's summation formula $n(n+1)/2$ finds expected totals in $O(1)$ arithmetic steps.
XOR method prevents potential integer overflow in languages with fixed integer limits.
Both strategies achieve optimal $O(n)$ time and $O(1)$ space.