You're handed an array nums of n distinct integers. Every value is drawn from the range [0, n] — that's n + 1 possible numbers for only n slots, so exactly one value from that range never shows up.
Return that single missing number.
For nums = [3, 0, 1] we have n = 3, so the full range is [0, 3] = {0, 1, 2, 3}. The array holds 0, 1, 3 — the only absentee is 2, so the answer is 2.
Input: nums = [3,0,1] Output: 2 n = 3, so the range is [0,3]. Every number appears except 2.
Input: nums = [0,1] Output: 2 n = 2, so the range is [0,2]. 0 and 1 are present, so 2 is missing.
Input: nums = [9,6,4,2,3,5,7,0,1] Output: 8 n = 9, so the range is [0,9]. Every number is present except 8.
- n == nums.length - 1 <= n <= 10^4 - 0 <= nums[i] <= n - All the numbers of nums are unique.
Missing Number is a small puzzle with a big idea: to find what's absent, you don't have to search for it — you can compare what the total should be against what it is, and read the gap directly. That "expected minus actual" move (and its overflow-proof XOR cousin) reappears in checksums, ledgers, and error-detecting codes.
0 + 1 + ... + n = n(n+1)/2. Knowing the expected total in O(1) is what makes the trick constant-space.O(1) "have I seen this value?" check — the stepping-stone approach between brute force and the sum trick.a ^ a = 0, so XORing paired values cancels them — an alternative that never overflows.Given an array nums of n distinct integers drawn from [0, n] (that's n+1 candidates for n slots), return the single value that's missing.
Worked example — nums = [3, 0, 1], so n = 3
expected sum of 0..3 = 3·4/2 = 6 actual sum = 3 + 0 + 1 = 4 missing = 6 − 4 = 2 ✓
“Is the range [0, n] or [1, n]?”
[0, n] — n+1 candidates for n slots. This decides whether the expected sum is n(n+1)/2 or something else.
“Are all values guaranteed distinct?”
Yes. The sum and XOR tricks rely on there being exactly one absentee and no duplicates.
“Can the missing number be 0 or n itself?”
Yes — [1,2,3] misses 0; [0,1,2] misses 3. The sum formula handles both with no special-casing.
“Just the single missing value?”
Yes. Confirm there's exactly one so you can commit to the aggregate trick.
“Could the sum overflow?”
With n up to 10^4 the expected sum is ~5×10⁷ (safe in 32-bit), but it's a habit to widen to 64-bit — or use XOR, which can't overflow at all.
A few quick questions.
The numbers come from 0 to n inclusive, with exactly one missing and no duplicates?
Can the missing value be 0 or n itself?
I'll aim for O(n) time and O(1) space — compare the expected total against the actual.
If overflow is a worry, I can XOR instead of sum.
The brute force asks "is 0 here? is 1 here? ..." and searches for each. But you never actually need to locate the absentee. An aggregate over all values already encodes it: whatever the full set contributes minus what's present is exactly the missing piece.
The full range 0..n sums to n(n+1)/2 (Gauss). Subtract the sum of the array's values and the remainder is the one number that never contributed — O(n) to add them up, O(1) extra space.
XOR 0 ^ 1 ^ ... ^ n together with every array value. Each present number appears twice (once from the range, once from the array) and cancels to 0; only the missing number is left. Same O(n)/O(1), with no risk of a large sum overflowing.
| Roll call | Hash set | Gauss sum | |
|---|---|---|---|
| Idea | Search for each candidate | Membership checklist | Expected total − actual total |
| Time | O(n²) | O(n) | O(n) |
| Space | O(1) | O(n) | O(1) |
The full code for all three is in the Approaches selector below.
Key takeaway
To find a single missing element from a known range, compare an aggregate of the full range against the aggregate of what's present: expected sum n(n+1)/2 minus the actual sum leaves the missing value in O(n) time and O(1) space. XOR gives the same result without any overflow risk.