Math & Bit Manipulation · LC #268
Missing Number
Find the missing integer in [0..n] from an n-element array in O(n) time and O(1) space using Gauss's sum formula or XOR cancellation.
Statement
Problem & Approach
Problem statement, sample I/O, and key reasoning.
Given an array containing `n` distinct numbers in the range `[0, n]`, return the one missing number.
Sample I/O
Input: nums = [3,0,1] Output: 2 Input: nums = [9,6,4,2,3,5,7,0,1] Output: 8
Intuition
How to Think About It
Intuition
The expected sum of [0..n] is fixed by Gauss's formula `n*(n+1)/2`. Subtracting the actual array sum isolates the missing number. Alternatively, XOR all indices [0..n] with all array values - every present number appears twice (once as index, once as value) and cancels, leaving the missing number.
Core Concept
Gauss method: `missing = n*(n+1)/2 - sum(nums)`. XOR method: `result = 0; for i in 0..n: result ^= i; for x in nums: result ^= x; return result`. Both are O(n) time, O(1) space.
When to use
Finding a single missing value in a near-complete sequence; detecting a dropped packet in a stream; checksum validation.
When NOT to use
When multiple numbers are missing (need a different approach - sort, bit array, or cycle detection). When integers may overflow `n*(n+1)/2` (use XOR method or long arithmetic).
Key Insights
What to Know Cold
- Gauss sum is the simplest: one subtraction after computing total and actual sums.
- XOR method avoids any risk of integer overflow - useful when n is very large.
- The XOR approach generalises elegantly: XOR of [0..n] ^ XOR of array values, pairs cancel.
- For the range [1..n] (no zero), the formula adjusts to `n*(n+1)/2 - sum` - same idea.
- Both approaches assume exactly one missing number; they break if there are multiple missing values.
1 example
Worked Examples
Gauss and XOR on [3,0,1]
n=3, expected sum=6, actual sum=4, missing=2
Gauss: 3*4/2=6; sum([3,0,1])=4; 6-4=2. XOR: (0^1^2^3)^(3^0^1)=2.
missingNumber([3,0,1]); // 2 // Gauss: expected=6, actual=4 → 2 // XOR: 0^1^2^3 = 0, then ^3^0^1 = 2
Two independent O(1)-space proofs of correctness - good to mention both in interview.