Missing Number
Find the one number missing from 0..n, three different ways — and see why two of them cannot overflow
Problem Statement
Given an array containing n distinct numbers taken from the range 0..n, find the one number that is missing.
Input: nums = [3, 0, 1] n = 3, range is 0..3
Output: 2
Input: nums = [0, 1] n = 2, range is 0..2
Output: 2
Input: nums = [9,6,4,2,3,5,7,0,1]
Output: 8Intuition
Three solutions, and comparing them is the point of the problem.
The set
Put everything in a set, then check 0..n for the one that is absent. O(n) time, O(n) memory. Correct and unremarkable.
The sum
The numbers 0..n have a known total. Subtract what is actually there, and the difference is what is missing.
nums = [3, 0, 1], n = 3
expected 0+1+2+3 = 6 (formula: n(n+1)/2)
actual 3+0+1 = 4
missing 6 - 4 = 2O(n) time, O(1) memory, and it is genuinely elegant. But it builds a large intermediate value — for n = 100,000 the expected sum is about 5 billion — which overflows a 32-bit integer.
The XOR
Same shape as the sum, but with an operation that cannot overflow.
The insight
XOR everything in the array and every number in 0..n into one running total.
Every value that is present appears twice — once from the array, once from the range — and cancels itself. The missing number appears only once, from the range. It is the sole survivor.
indices/range: 0 1 2 3
array: 3 0 1
0^1^2^3 ^ 3^0^1
= (0^0) ^ (1^1) ^ (3^3) ^ 2
= 0 ^ 0 ^ 0 ^ 2 = 2This is Single Number with a twist: there, the pairs were handed to you. Here you create the pairs by supplying the partners yourself.
Approach
Start the total at n
The range 0..n has n + 1 values but the array has only n slots. Seeding with n covers the extra one, so a single loop can then handle indices 0..n-1.
For each index, XOR in both the index and the value there
The index contributes a number from the range; the value contributes a number from the array.
Whatever is left is the missing number
Everything present got XOR-ed exactly twice and cancelled. The absent value got XOR-ed once.
Solution
def missing_number(nums: list[int]) -> int:
"""Find the value missing from 0..n.
Every present value is XOR-ed twice (once as an index, once as a
value) and cancels. The missing one is XOR-ed only once.
"""
result = len(nums)
for i, num in enumerate(nums):
result ^= i ^ num
return resultPython integers never overflow, so the sum version is also safe here:
n * (n + 1) // 2 - sum(nums). The XOR version is still preferable, because it ports to languages where the sum is not safe.
Complexity Analysis
Time Complexity
O(n)
Space Complexity
O(1)
Time — a single pass, two XORs per element.
Space — one integer.
The three solutions compared
| Time | Space | Overflow risk | Needs sorting | |
|---|---|---|---|---|
| Set | O(n) | O(n) | No | No |
| Sum | O(n) | O(1) | Yes | No |
| XOR | O(n) | O(1) | No | No |
| Sort then scan | O(n log n) | O(1) | No | Yes |
All four are correct. XOR is the only one with no cost and no caveat — which is why it is the answer worth remembering.
Edge Cases
Related Problems
- Single Number — the same cancellation, with the pairs already present
- Find Pivot Index — another "expected total minus actual" argument
- Contains Duplicate — the set-based approach, when memory is not restricted