Missing Number
Missing Number is an easy Bit Manipulation problem from the Blind 75. The key pattern is xor or sum, and a good solution runs in O(n) time.
Problem
An array contains distinct values from 0 through n with one absent; return the absent value.
Examples
Example 1
Input
[0,1,3,4]Output
2Example 2
Input
[4,1,0,2]Output
3Example 3
Input
[0,1]Output
2Approach
XOR every index and value together; matching pairs cancel and only the missing number remains. The expected sum minus the actual sum also works.
| Pattern | XOR or sum |
|---|---|
| Time | O(n) |
| Space | O(1) |
Watch out for
The range is 0 to n, so n itself can be the missing value.