Missing Number XOR

Find the missing integer in a sequence using XOR, without extra space.

xor bitwise arrays math

You are given a list `nums` of length `n` that contains `n` distinct integers chosen from the range `0` to `n` (inclusive), so exactly one number from that range is missing. Write a function `missing_number(nums)` that returns the missing integer.

Your solution should run in O(n) time and O(1) extra space. Using XOR is recommended, but any approach that meets the complexity is acceptable.

Constraints

`0 <= len(nums) <= 10^5`
Each element in `nums` is a distinct integer between `0` and `len(nums)` inclusive.
The input may be empty (then the missing number is `0`).
Time: O(n). Space: O(1).

Example

>>> missing_number([3, 0, 1])
2
>>> missing_number([0, 1])
2
>>> missing_number([9, 6, 4, 2, 3, 5, 7, 0, 1])
8
>>> missing_number([])
0

10 points ~15 min

Recent Submissions

No submissions yet — hit Run Tests to try!

Hints

Think about XOR properties: x ^ x = 0 and x ^ 0 = x.

XOR all numbers from 0 to n, then XOR that with every element in nums.

The result is the missing number because every present number cancels out.

An empty list means no numbers from 0 to 0 are present, so the missing number is 0.

Test Results

Press Ctrl+Enter or click Run Tests to execute your code.