Missing Number is a tidy little puzzle that rewards a clever observation instead of brute force. It teaches a reusable trick: when a set of numbers is almost complete, compare what you have against what you should have.
Problem. Given an array nums containing n distinct numbers taken from the range 0, 1, ..., n,
exactly one number in that range is missing. Return the missing number.
Example: nums = [3, 0, 1], so n = 3 and the range is 0, 1, 2, 3. The number 2 never appears, so
the answer is 2.
The slow way first
The obvious idea: for each candidate value from 0 to n, scan the whole array to see if it is present. The first one you cannot find is the answer. That works, but every scan is O(n) and you do it up to n times — O(n²) overall.
The question to ask: I know exactly which numbers should be here. Is there a shortcut that uses that? There is — and it does not even need extra memory.
The idea: compare the totals
The numbers 0, 1, ..., n always add up to the same fixed amount, given by Gauss's formula: expected = n(n+1)/2. If one of them is missing, the actual sum of the array will fall short by exactly that missing value. So compute both sums and subtract.
For nums = [3, 0, 1]: expected = 3*4/2 = 6, the array sums to 3 + 0 + 1 = 4, and 6 - 4 = 2.
Walk through it
Step through the animation. The pointer i scans left to right, and the running total accumulator grows as each value is added in. We already know expected = 6 from the formula. After the last element is counted, total = 4, so the gap 6 - 4 = 2 pops out as the missing number.
Pseudocode
n = length of nums
expected = n * (n + 1) / 2 # sum of every number 0..n
total = 0
for each num in nums:
total = total + num # accumulate the actual sum
return expected - total # the shortfall is the missing numberThe Python solution
def missing_number(nums):
n = len(nums)
expected = n * (n + 1) // 2
total = 0
for num in nums:
total += num
return expected - totaln = len(nums)is the count of elements, so the full range is0..n.expected = n * (n + 1) // 2is Gauss's closed-form sum of0..n— computed in O(1), no loop needed.totalaccumulates the actual sum of the array as we walk it once.total += numadds each value in turn; this single pass is the only loop.return expected - totalis the punch line: the amount the actual sum falls short by is the missing value.
Complexity
| Case | Time | Notes |
|---|---|---|
| Brute force (scan per candidate) | O(n²) (slow) | n lookups, each O(n) |
| Sum formula (this solution) | O(n) (moderate) | one pass to add, O(1) formula |
O(1) (fast)This beats the hash-set approach too: a set would also be O(n) time but cost O(n) extra space, while the sum trick needs only a couple of variables — O(1) space.
When this pattern shows up
When the input is a near-complete set of known numbers, think about invariants you can precompute: a sum, an XOR, a count. Comparing the ideal value against the actual one often collapses a search into a single pass. The same Gauss-sum move solves problems framed as "one number is missing" or "find the duplicate."
For very large n, the expected sum can overflow fixed-width integers in some languages. Python integers
are unbounded so it is safe here, but in Java or C an XOR-based solution avoids the overflow entirely
while keeping O(n) time and O(1) space.
Practice
For nums = [0, 1] the range is 0..2. What is expected, what is the actual total, and which number is missing?
1. Why does subtracting the array sum from n(n+1)/2 give the missing number?
2. What is the extra space used by the sum-formula solution?
3. For nums = [3, 0, 1], what are expected and total?
4. Why might an XOR-based version be preferred over the sum in some languages?