#268
Missing Number
Easy XOR
- Read
- Understand
- Hints
- Approach
- Solution
- Solved
?The problem
The array holds n distinct numbers taken from 0..n. Exactly one is missing; find it.
This is a short summary in our own words. Read the full statement and examples on LeetCode: open problem ↗
◎Understanding
Really asking: numbers 0..n with one missing; which one?
Why this works: XOR all indexes 0..n with all values. Every number that is present shows up twice and cancels.
Example: nums = [3, 0, 1], n = 3
start x = 3^0^3 → 0, ^1^0 → 1, ^2^1 → 2answer 2
✦Hints open one at a time
XOR every index 0..n with every value. Everything present appears twice.
The sum formula n(n+1)/2 also works, but XOR can't overflow.
↗Approach
Start with x = n, then XOR in each index i and each value nums[i]. Every number that is present cancels, leaving the missing one.
</>Solution (Java)
class Solution {
public int missingNumber(int[] nums) {
int x = nums.length; // include n
for (int i = 0; i < nums.length; i++) {
x ^= i ^ nums[i];
}
return x;
}
}!Common mistake
Forgetting to include n itself in the XOR (the indexes only go to n - 1).
Complexity
- Time: O(n).
- Space: O(1).
