TL;DR
XOR every index with every value so pairs cancel and the missing number remains — O(n) time, O(1) space, overflow-proof.
Approach 1 — Brute force: a hash set
The naive intuition: record what’s present, then scan 0..n for the gap.
class Solution:
def missingNumber(self, nums: list[int]) -> int:
seen = set(nums)
for i in range(len(nums) + 1):
if i not in seen:
return i
return -1 # unreachable given the constraints
Complexity: O(n) time, O(n) space for the set.
Why we can do better: correct, but the follow-up bans the extra O(n) space. The next two approaches reach O(1).
Approach 2 — Gauss sum (arithmetic)
The insight: the numbers 0, 1, ..., n add up to a closed-form total n(n + 1) / 2. Whatever is missing equals that expected total minus the actual sum of the array.
class Solution:
def missingNumber(self, nums: list[int]) -> int:
n = len(nums)
expected = n * (n + 1) // 2
return expected - sum(nums)
Walkthrough on [3, 0, 1]: n = 3, expected = 3 * 4 // 2 = 6, sum(nums) = 4, so 6 - 4 = 2. ✓
Complexity: O(n) time, O(1) space.
Caveat: in a fixed-width language, expected and sum(nums) can each overflow for large n even though their difference fits. Python’s big integers dodge this, but that fragility is exactly why the XOR version is often preferred.
Approach 3 — XOR of indices and values
The insight: XOR cancels equal operands (x ^ x = 0) and is order-independent, so if you XOR together both the indices 0..n and all the values in nums, every number that is actually present appears exactly twice — once contributed by its index position and once by its value — and annihilates itself. The one missing number is contributed only by its index, so it is the lone survivor. Since XOR never grows the operands, there is no overflow.
class Solution:
def missingNumber(self, nums: list[int]) -> int:
result = len(nums) # seed with n; the loop covers indices 0..n-1
for i, num in enumerate(nums):
result ^= i ^ num
return result
We seed result with n because enumerate only yields indices 0..n-1; seeding covers the final index n, completing the full index set 0..n.
Walkthrough on [3, 0, 1] (result starts at 3):
| i | num | i ^ num | result after |
|---|
| — | — | — | 3 |
| 0 | 3 | 3 | 3 ^ 3 = 0 |
| 1 | 0 | 1 | 0 ^ 1 = 1 |
| 2 | 1 | 3 | 1 ^ 3 = 2 |
Returns 2. ✓ Notice 3 (index 0’s value) and the index 3 from the seed cancel; 0 and 1 each cancel their own index; index 2 never meets a value 2, so 2 is left.
Complexity: O(n) time, O(1) space, no overflow.
Common pitfalls
- Range off by one: the search/loop must cover
0..n inclusive (n + 1 values), not 0..n-1.
- Forgetting the seed in XOR: without initializing
result = n, the highest index is never folded in and the answer is wrong whenever the missing number isn’t n.
- Overflow in the sum version: fine in Python, but flag it in languages with fixed-width integers — that’s the whole reason to prefer XOR.
- Assuming the array is sorted: it isn’t; both the sum and XOR methods work regardless of order (a virtue of commutative operations).
Pattern takeaway
When elements pair up and exactly one is unmatched, XOR is the tool: fold everything together and matched pairs vanish (x ^ x = 0), leaving the odd one out. It beats the sum trick whenever overflow is a concern, because XOR never enlarges its operands.