Missing Number — Step-by-Step Visualization

Algorithm Pattern

XOR or Gauss Sum

Key Idea

We know that the sum of the first `n` numbers is `n * (n + 1) / 2`. If we subtract the sum of the numbers in the array from this expected sum, the result is the missing number. Alternatively, XORing all indices `[0, n]` and all numbers in the array will also reveal the missing number because `x ^ x = 0`.

Step-by-Step Approach

1. Option 1 (Sum):
2. Calculate `expectedSum = n * (n + 1) // 2`.
3. Calculate `actualSum = sum(nums)`.
4. Return `expectedSum - actualSum`.
5. Option 2 (XOR):
6. Initialize `res = len(nums)`.
7. For `i, n` in `enumerate(nums)`:
8. `res ^= i ^ n`.
9. Return `res`.

Common Gotchas

• The array contains `n` numbers, but the range is `[0, n]`, so there's exactly one missing.
• Be careful with indices if using XOR.