Coding · Easy · Free
Find missing number in [0..n] using XOR
CodingBit ManipulationFresher
Approach
- XOR index i with all nums; pairs cancel.
- Equivalent to XOR all 0..n then all array values.
Java Solution
Java
public int missingNumber(int[] nums) {
int xor = nums.length;
for (int i = 0; i < nums.length; i++) xor ^= i ^ nums[i];
return xor;
}| Complexity | |
|---|---|
| Time | O(n) |
| Space | O(1) |
Interview tip: Sum formula is alternative; XOR avoids overflow concerns.