Missing Number
You get a list nums of n distinct integers, each between 0 and n. The range from 0 to n holds n+1 numbers, so exactly one of them is not in the list. Return that missing number.
Function
- numsinteger-array
- n distinct integers from the range 0 to n, in any order
- Returnsinteger
- the one number from 0 to n that is not in nums
Constraints
n == nums.length1 ≤ n ≤ 1040 ≤ nums[i] ≤ n- All the values in
numsare distinct.
Examples
- Input
- nums = [4, 2, 0, 1]
- Output
- 3
- Explanation
- The list has 4 values, so the range is 0 to 4. It holds 0, 1, 2 and 4, and 3 is the only number with no match.
- Input
- nums = [1]
- Output
- 0
- Explanation
- With one value the range is 0 and 1. The list holds 1, so 0 is missing.
- Input
- nums = [0, 1, 2]
- Output
- 3
- Explanation
- Every number below 3 is present, so the missing one is 3 itself, the top of the range. It is not an index of the list, which is why the top needs care.
+13 hidden tests on Submit
Follow-up
If the list came sorted, could you find the missing number in O(log n) time with binary search?
Hints
Open them one at a time. Each one gives away a little more.
You know exactly which numbers the list should hold: every integer from
0ton. Is there one number you can compute for that full range and compare with the same number computed for the list?The integers from
0tonadd up ton(n+1)/2, and the list's sum is smaller by exactly the missing value. XOR works the same way without any risk of overflow, because a value XOR-ed with itself is0.Walk the list once with a running XOR. Start it at
n, and at every indexiXOR in bothiandnums[i]. Every number that appears twice cancels, and the missing one is left.
Solution
You know exactly what the list should contain: every integer from 0 to n. Searching for each of those numbers one by one works but repeats a full scan per number. Instead, squeeze the full range and the list into one summary value each, the sum or the XOR, and the difference between the two is the missing number. That takes one pass and no extra memory.
Check every candidate
Correct, but does not finish on the largest tests
Intuition
The answer is one of the n+1 numbers from 0 to n. Take them in order and scan the list for each one. The first candidate that no value matches is the missing number.
This is correct because every number in the range is either in the list or is the answer, and the list has no duplicates, so exactly one candidate fails the search.
It is slow because every candidate costs a scan of up to n values. When the gap sits near the top, almost every candidate is searched for: with n = 10^4 and the gap near the end, that is around 5 × 10^7 comparisons. Doubling the list makes the work four times larger.
Algorithm
- Loop
candidatefrom0up ton, inclusive. - Scan
numsfor a value equal tocandidate. - If the scan finds it, move on to the next candidate.
- If the scan ends without a match, return
candidate.
def missingNumber(nums):
n = len(nums)
for candidate in range(n + 1):
# "in" on a list scans it from the start: O(n) per candidate.
if candidate not in nums:
return candidate
return -1Subtract the sum from the expected sum
Intuition
If nothing were missing, the list would hold every number from 0 to n, and those add up to n(n+1)/2. The real list is that full set with one number taken out, so its sum falls short by exactly that number.
For [4, 2, 0, 1], n is 4 and the full range sums to 4 × 5 / 2 = 10. The list sums to 7, and 10 minus 7 leaves 3.
One pass adds up the list, so the time is O(n), and you keep one running total. Here the full sum is at most about 5 × 10^7, which fits a 32-bit integer. For much larger n the formula overflows a 32-bit int, so the Java, C, C++, C# and Rust versions do the arithmetic in 64 bits.
Algorithm
- Let
nbe the length ofnums. - Compute the full sum
n(n+1)/2. - Add up every value in
nums. - Return the full sum minus the list's sum.
def missingNumber(nums):
n = len(nums)
expected = n * (n + 1) // 2
return expected - sum(nums)XOR the indexes with the values
Intuition
XOR cancels pairs. a ^ a is 0, a ^ 0 is a, and the order of the operations does not matter. So if you XOR a bag of numbers where everything appears twice except one value, the pairs vanish and that value is what remains.
Build such a bag from the problem: the indexes 0 to n plus the values in nums. A number that is in the list shows up once as an index and once as a value, so it cancels. The missing number shows up only as an index, so it survives. The loop visits the indexes 0 to n-1, so start the result at n to include the last one.
For [4, 2, 0, 1]: start at 4, then XOR in 0 and 4, 1 and 2, 2 and 0, 3 and 1. The 4s, 2s, 1s and 0s all cancel, and 3 is left. This is one pass with one running value, and unlike the sum it never grows past the bits that n already uses, so it cannot overflow.
Algorithm
- Set
resultton, the length ofnums. - For each index
i, XORresultwithiand withnums[i]. - Return
result.
def missingNumber(nums):
# Start with n, the one index the loop below never reaches.
result = len(nums)
for i, value in enumerate(nums):
result ^= i ^ value
return result
Pitfalls and edge cases
Most wrong answers come from the two ends of the range.
- Forgetting that
nitself can be missing. In[0, 1, 2]the answer is 3, which is not an index of the list. The XOR version must start atn, and a sorted scan that looks for the firstnums[i] != imust returnnwhen every position matches. - Using the wrong range size. The numbers run from
0ton, which isn+1numbers, so the full sum isn(n+1)/2, not(n-1)n/2. - Assuming
0is always present. In[1]the answer is 0, and code that starts its search at 1 misses it. - Overflow in the sum version. In 32-bit arithmetic the product
n(n+1)overflows oncenpasses about 46,000, before the division by 2 can help, andn(n+1)/2itself stops fitting near 65,000. Use 64-bit arithmetic, or XOR.
Frequently asked questions4
What is the time complexity of Missing Number?
The sum and XOR solutions both run in O(n) time with O(1) extra space, since they read each value once and keep one number. Searching the list for every candidate takes O(n²). Sorting first and looking for the gap takes O(n log n).
Why does XOR find the missing number?
XOR-ing a number with itself gives 0, XOR-ing with 0 changes nothing, and the order does not matter. When you XOR all the indexes from 0 to n together with all the values, every number that is in the list appears twice and cancels. The missing number appears only once, as an index, so it is the result.
Should you use the sum formula or XOR?
Both take one pass and constant memory. The sum is the easier one to explain, but in 32-bit arithmetic the product n(n+1) overflows once n passes about 46,000, so you need 64-bit arithmetic. XOR never overflows. In Python, Ruby and other languages with unlimited integers the difference disappears.
Can you solve Missing Number with a hash set?
Yes. Put every value in a set, then check 0 to n and return the first number the set lacks. That runs in O(n) time but uses O(n) extra memory, which the sum and XOR methods avoid.
Similar problems
Problems that use the same ideas. Solving two or three of them is what makes a pattern stick.
Python
def missingNumber(nums):
# Write code hereCase 1
Case 2
Case 3
Input
nums = [4, 2, 0, 1]
Expected
3