Find Missing Number
Array has n numbers from 0 to n, one missing. XOR all array elements with all numbers 0 to n. The pairs cancel, leaving only the missing number. Alternatively, use expected sum − actual sum.
How It Works
Given n distinct numbers drawn from the range 0 to n with exactly one absent, XOR every array element together with every number from 0 to n. Each present number appears twice in that combined stream — once from the array, once from the range — and cancels to zero, so the surviving value is precisely the missing number. A single loop, one accumulator, done.
The arithmetic alternative computes the expected sum n*(n+1)/2 and subtracts the actual sum, which is equally O(n) time and O(1) space but can overflow fixed-width integers for large n, whereas XOR never grows beyond the operand width. Both approaches beat sorting (O(n log n)) and hash sets (O(n) extra space). Cyclic sort is a third option when the array may be mutated.
Step-by-Step Visualization
Code
static int missingNumber(int[] nums) {
int xor = nums.length;
for (int i = 0; i < nums.length; i++) xor ^= i ^ nums[i];
return xor;
}
// missingNumber(new int[]{3,0,1}) → 2Tips & Gotchas
Practice Problems
- 1Missing Number
- 2Find All Numbers Disappeared in an Array
- 3Set Mismatch
About the XOR Tricks Pattern
XOR has a magical property: a ⊕ a = 0 and a ⊕ 0 = a. So if you XOR all elements in a list where every element appears twice except one, all pairs cancel out and the unique element survives.
Key tricks: n & (n−1) clears lowest set bit (power-of-2 check). XOR of all elements cancels pairs. Bit masks can represent subsets for DP. These are often O(1) space solutions.
Common Bit Manipulation Interview Problems
- Single Number
- Number of 1 Bits
- Counting Bits
- Missing Number
- Reverse Bits
- Power of Two
Frequently Asked Questions
Should I use the XOR method or the sum formula?
Both are O(n) time and O(1) space, so either passes. XOR has the edge in languages with fixed-width integers because the accumulator can never overflow, while the sum n*(n+1)/2 can exceed 32 bits for large n. In Python or with 64-bit arithmetic the difference is cosmetic.
What if several numbers are missing instead of one?
Plain XOR only isolates a single unknown. For multiple missing values, mark presence in place by negating the value at each seen index (cyclic-sort style), then report indices still holding positive values — still O(n) time and O(1) extra space.