The problem
A list contains n different numbers taken from 0, 1, …, n, so exactly one is missing. Find the missing number.
Input: [3, 0, 1] Output: 2
Picture it
Picture a roll call: students numbered 0 to n should all be present but one is missing. Add up 0 + 1 + … + n (what the total should be) and subtract the numbers that actually answered. The difference is the missing student’s number.
How to recognise it
- The values come from a known complete range (0 to n) with exactly one missing, and each value appears at most once.
- If you know what the complete set adds up to, the missing value is the difference between that and what you have.
- The same "cancel what is present" idea works with XOR (
^), which is why it sits with bit manipulation. - n is up to 10^4, and the follow-up asks for O(n) time and O(1) extra space.
Start with brute force
Check each candidate 0, 1, ..., n and return the first one that is not in the list.
def missing_brute(nums):
for i in range(len(nums) + 1):
if i not in nums:
return i
i not in nums scans the list, so this is O(n²) time: up to about 5 × 10^7 comparisons for n = 10^4, slow in Python. A set makes each lookup O(1) and the whole thing O(n), but it needs O(n) extra space.
From brute force to the idea
- Find the waste. We search for each candidate separately, but we only need one number: what is absent.
- Know the full total. The numbers 0 to n add up to n(n + 1)/2 (Gauss's formula). Here n is
len(nums), because the list holds n of the n + 1 values. - Subtract what is present. Every value in the list cancels its share of the total. What remains is the one value that never got subtracted.
- Use integer division.
n * (n + 1) // 2is exact, because one of n and n + 1 is even.
This is the key idea: expected sum minus actual sum is the missing number, in one pass and one variable.
Python integers never overflow, so the total is safe. In languages with 32-bit integers the XOR version below avoids any risk of overflow.
The key idea
n(n + 1)/2 − sum(nums) (or XOR indices and values). O(n), O(1).
Python solution
def missing_number(nums):
n = len(nums)
total = n * (n + 1) // 2 # roll call should add up to this
for x in nums:
total -= x
return totalIn the interactive version each line lights up as the animation runs, and you can type your own input to see the algorithm handle it.
Complexity
| Approach | Time | Space |
|---|---|---|
Brute force (in on a list) | O(n²): a scan for each candidate | O(1) |
| Set of present values | O(n) | O(n): the set |
| Expected sum (shown code) | O(n): one subtraction per number | O(1): one running total |
Edge cases
- The missing number is n (
[0, 1]): the total 3 minus 0 and 1 leaves 2. - The missing number is 0 (
[1]): the total 1 minus 1 leaves 0. - Single element
[0]: returns 1. - Unsorted input (
[9, 6, 4, 2, 3, 5, 7, 0, 1]): order does not matter; returns 8. - Broken promise (a duplicate, or a value above n): the result is meaningless, for example
[5, 0]returns −2. The code does not check.
Common mistakes
- Using n = the largest value in the list instead of
len(nums): if n itself is missing, the largest value is n − 1 and the total is wrong. - Using the formula for 1 to n with the wrong n, such as
n * (n - 1) // 2. - Sorting first and looking for a gap: correct, but O(n log n), and easy to miss the case where the gap is at the end.
- Using
/instead of//, which gives a float such as2.0.
Find the missing number again, but using XOR instead of a sum, so no total can grow large. Describe your approach, then write it if you like.
Compare with our answer
XOR every index 0 to n − 1, the value n, and every number in the list. Each present value appears twice (once as an index or as n, once in the list) and cancels; the missing one appears once and remains.
def missing_xor(nums):
acc = len(nums) # n itself, the one index enumerate never gives
for i, x in enumerate(nums):
acc ^= i ^ x
return acc
Time O(n), space O(1). missing_xor([3, 0, 1]) is 2.
A strong answer mentions: pairing each expected value with the list values so they cancel, including n (which enumerate does not produce), and that XOR never overflows.
1. A ticket roll should hold numbers 1 to n with one ticket missing and no repeats. Which approach fits best?
Same pattern with the range 1 to n: the expected total minus the actual total is the missing ticket, in O(n) and O(1) space. Sorting costs O(n log n), scanning costs O(n²), and the missing ticket may be in the middle.
2. Why must the shown code use n = len(nums) rather than max(nums)?
The list holds n numbers from 0 to n, so its length is always n. If n is the missing value, the largest present value is n − 1, and the expected total would leave out n, giving 0 instead of n. max is O(n) once, not per item.
3. What does the shown code return for [0, 1]?
n = 2, so the expected total is 0 + 1 + 2 = 3. Subtracting 0 and 1 leaves 2, the missing value at the end of the range.
Score 60% or more and the lesson is marked complete.