Missing Number
EasyBit manipulation
nums holds n different numbers taken from the range 0 to n, so exactly one number of that range is missing. Return it.
Aim for O(n) time and O(1) extra space.
Examples
Input: nums = [4, 0, 1, 3] Output: 2
The range is 0 to 4, and 2 is the one not there.
Input: nums = [1, 2, 0] Output: 3
Three numbers means the range is 0 to 3, so the missing one is 3, the top of the range.
Constraints
1 ≤ n ≤ 10⁴, wherenisnums.length0 ≤ nums[i] ≤ n- All values in
numsare different.
Stuck?
Hint 1
You know the sum of every number from 0 to n. Compare it with the sum of nums.
Hint 2
Or XOR every index, n and every value together: each number that is present cancels itself out, and the missing one is left.
The idea
XOR a number with itself and you get 0, and the order of XORs does not matter. XOR every number from 0 to n together with every value in nums: each number that is present appears twice and cancels out, and the missing one is all that remains.
Time O(n)Extra space O(1)
Try it again with the idea in mind, or go through the code one step at a time.
The code, step by step
Step 1 of 3
Start with n. The indexes below only run from 0 to n - 1, so n has to be put in here.
function missingNumber(nums) { let missing = nums.length; for (let i = 0; i < nums.length; i++) { missing ^= i ^ nums[i]; } return missing;}The trap
Sorting and looking for the first position whose value differs from its index finds a gap in the middle or at 0. When the missing number is n, the top of the range, every position matches, the loop finds nothing, and the function returns -1 instead of n. Sorting also takes O(n log n) time.
function missingNumber(nums) { const sorted = [...nums].sort((a, b) => a - b); for (let i = 0; i < sorted.length; i++) if (sorted[i] !== i) return i; return -1; // forgets that n itself can be the missing one}