The list nums holds n different numbers, all from the range 0 to n. That range has n + 1
numbers, so exactly one of them is missing. Return the missing number.
Aim for O(n) time and a constant amount of extra memory.
Example 1
- Input
- nums = [2, 0, 4, 1]
- Output
- 3
Example 2
- Input
- nums = [0, 1]
- Output
- 2
Constraints
numsholds n numbers, where 1 ≤ n ≤ 10⁴.- Every number is between 0 and n, and no number appears twice.
Show the pattern
Bit manipulation, Math and matrices
The list holds every number from 0 to n but one. XOR-ing every index and every value cancels each number that is present (`x ^ x = 0`) and leaves the missing one; the sum formula does the same job.
Show the approach
The numbers 0 to n appear once each among the indices 0 … n − 1 together with n. Among the
values, every number appears once too, except the missing one.
XOR all of them together: start from n, and XOR in each index i and each value nums[i].
Every number that is present appears twice and cancels (x ^ x = 0), so what is left is the
missing number.
Summing works the same way: the missing number is n(n + 1) / 2 − sum(nums).
Time: O(n) · Space: O(1)