Easy · XOR Cancellation
Understand → Visualise → Practice.
The array contains distinct values from 0 through n with one missing. Return the missing value using XOR.
XOR every index 0..n and every array value together. Each present number appears twice and cancels; only the missing number remains.
Set answer = n, because indices only run to n − 1.
For each i, do answer ^= i ^ nums[i].
Pairs cancel because x ^ x = 0, leaving the missing value.
O(n) time and O(1) space.
Starting from 0 instead of n forgets the number n itself, which may be the one missing.
Read the full guide first: Bit Manipulation and Bitmask Patterns.
Guest mode lets you understand, visualise and run the sample tests. Create a free account to submit and save your solutions.