The problem
An array holds n different numbers taken from 0 to n — so exactly one is missing. Return it.
Examples
01
- Input
nums = [3, 0, 1]
- Output
2
02
- Input
nums = [0, 1]
- Output
2
03
- Input
nums = [9, 6, 4, 2, 3, 5, 7, 0, 1]
- Output
8
Constraints
- 1 ≤ n ≤ 10⁴
- 0 ≤ nums[i] ≤ n
- All the numbers are different.
The idea
XOR together every number from 0 to n and every number in the array. Each number that is present appears twice — once in each list — and cancels, as in Single Number. The missing one appears only once, so it is what remains.
Pairing each index i with the value nums[i] in one loop covers 0 to n − 1, and starting from n covers the last one. (Adding them up and subtracting also works, but the sum can overflow; XOR cannot.)
- Time
- O(n)
- Space
- O(1)
Solution · every language run against every case
class Solution: def missingNumber(self, nums: List[int]) -> int: # XOR every index 0..n and every value: each number present cancels with its index, # leaving only the one that is missing. out = len(nums) for i, x in enumerate(nums): out ^= i ^ x return out