Sweaty Imposter

Missing Number (XOR)

EasyBitwise XORJuniorOpen on LeetCodeUpdated

You're given an array nums of n distinct integers, each taken from the range 0 to n inclusive, in no particular order. That range holds n + 1 values and the array holds only n, so exactly one value is missing. Return it. Use only O(1) extra space, and don't add the numbers up, since a running total can overflow a fixed-size integer. The missing value can be 0 or n itself.

Examples

nums = [3,0,1] returns 2

n = 3, so the values should be 0, 1, 2 and 3. The array has 0, 1 and 3, so 2 is missing.

nums = [0,1] returns 2

n = 2, so the range is 0 to 2. Both 0 and 1 are present, so the missing value is 2, the top of the range.

Constraints

  • 1 <= n <= 10^4
  • All values distinct in [0, n].

Hints

Hint 1

Could you cancel out everything you expect to see, so only what's missing remains?

Hint 2
A pointer toward the approach
Hint 3
The full approach, step by step

Drill This: Your Approach First

Approach

XOR together every index 0 to n - 1, the value n, and every element of nums. Each value that is present shows up twice in that combined XOR, once as an index (or as n) and once as an element, so it cancels to 0 and only the missing value remains. The code seeds the result with n, then folds in i ^ nums[i] for each position. O(n) time, O(1) space, and no addition that could overflow.

Time

O(n)

Space

O(1)

Pitfall

Forgetting n itself: the indices only run 0 to n - 1, so if you seed the result with 0 instead of len(nums), the case where n is the missing value fails. For nums = [0,1] you'd return 0 instead of 2.

Solutions

class Solution {
    public int missingNumber(int[] nums) {
        int result = nums.length;
        for (int i = 0; i < nums.length; i++) {
            result ^= i ^ nums[i];
        }
        return result;
    }
}
Drill This