One number from 0 to n is gone. Add up what 0 to n should total, subtract what you have, and the gap is the answer.
▼The problem
LeetCode 268 (Easy). Given an array nums of n distinct numbers taken from the range 0..n, return the one number in the range that is missing.
Example (LeetCode's third): nums = [9, 6, 4, 2, 3, 5, 7, 0, 1], n = 9 → 8.
The solution
def missingNumber(nums):
n = len(nums)
expected = n * (n + 1) // 2
return expected - sum(nums)Transcript
Missing Number. You're given n distinct numbers, each between zero and n. That range holds n plus one values, but you only have n numbers, so exactly one is missing. Find it.
Take nine numbers: nine, six, four, two, three, five, seven, zero, one. Put each in its locker, from zero to nine. Locker eight stays empty, so the answer is eight.
The obvious ways work, but cost something. Sort the numbers and look for the first gap: that takes n log n time. Or put every number in a set, then check zero to n: linear time, but a whole set of extra space.
Here's the trick. If nothing were missing, the lockers would add up to zero plus one plus two, all the way to n. That's n times n plus one, over two. Now add up the numbers you actually have. The difference is exactly the missing one.
In code, compute the expected total from n, subtract the sum of the list, and return it. Where big sums can overflow, XOR every index and every value instead. Matching pairs cancel out, and only the missing number survives.
Back to our example. N is nine, so a full set adds up to nine times ten over two: forty-five. Tally what we have: nine, fifteen, nineteen, twenty-one, twenty-four, twenty-nine, thirty-six, thirty-six, thirty-seven. Forty-five minus thirty-seven is eight. Locker eight.
One pass over the list, so the time is linear. One running total, so the space is constant.
Count what should be there, subtract what is. That's Missing Number.