Single number (XOR)
Why it exists
Problem: Given an array where every element appears exactly twice except for one, finding the unique element using a hash set or frequency map takes O(n) auxiliary space.
Naive approach: Count frequencies with a hash map, or sort the array first (taking O(n log n) time).
Better idea: Use the bitwise XOR operator to create a self-canceling accumulator. Because XOR is commutative and associative, all duplicate pairs will cancel each other out to 0, leaving only the single unique number. This achieves O(n) time and O(1) space.
Mental model
Pairs annihilate each other. If you throw everything into a blender, the identical twins cancel out, and only the single child remains.
Initialize a running result to 0. XOR every element into this running result. Since `x ^ x = 0` and `x ^ 0 = x`, order doesn't matter. The duplicates will zero each other out, and the accumulator will hold the unique element at the end.
Repeated decision: XOR this number into my running result -- for any value that appears twice, its two XORs will cancel to 0, so whatever survives at the end is the answer.
Explanation
To understand how XOR isolates the unique number, we must trace it at the binary level. Remember two core rules of XOR: anything XORed with itself is 0 (`a ^ a = 0`), and anything XORed with 0 is itself (`a ^ 0 = a`). Furthermore, XOR is commutative and associative, meaning `a ^ b ^ a` is the exact same as `a ^ a ^ b` (which reduces to `0 ^ b`, which is `b`).
Let's trace this on a small array: `[4, 1, 2, 1, 2]`.
We initialize our accumulator to 0 (`000`).
Step 1: XOR 4 (`100`)
`000 ^ 100 = 100` (accumulator is now 4)
Step 2: XOR 1 (`001`)
`100 ^ 001 = 101` (accumulator is now 5)
Step 3: XOR 2 (`010`)
`101 ^ 010 = 111` (accumulator is now 7)
Step 4: XOR 1 (`001`)
`111 ^ 001 = 110` (accumulator is now 6). Notice what happened: the `001` bit we added in step 2 just got toggled back off! The two 1s canceled each other.
Step 5: XOR 2 (`010`)
`110 ^ 010 = 100` (accumulator is now 4). The `010` bit we added in step 3 toggled off. The two 2s canceled each other.
At the end, all paired numbers vanished, and the accumulator holds `100` (decimal 4) -- our unique number. We found it in a single O(n) pass, using strictly O(1) space.
Common mistakes
- Trying to use a running SUM instead of XOR: A running sum does not cancel duplicates unless you know what the duplicates are and subtract them. Adding them just creates a larger number that can potentially overflow, and doesn't isolate the unique element.
- Assuming this generalizes to 'appears three times': If every element appears THREE times except one, simple XOR completely fails because `x ^ x ^ x = x`. That requires a different, significantly more complex multi-state bit manipulation trick (Single Number II).
Recall questions
- Why does the XOR trick find the single number?
- What is the time and space complexity of the XOR single number approach?
- Why is the XOR approach preferred over using a hash set?
Questions & answers
Find the unique element in an array where every other element appears exactly twice.
Iterate through the array, XORing every element into a single accumulator variable initially set to 0. Return the accumulator.
Approach: Direct application of the XOR cancellation trick.
Given an array containing n distinct numbers taken from 0, 1, 2, ..., n, find the one that is missing.
XOR all the array elements together, and also XOR that result with all numbers from 0 to n. The paired numbers cancel, leaving the missing number.
Approach: Pattern transfer: use XOR cancellation against an expected baseline to find a missing item, avoiding sum overflow.
Continue learning
Previous: Bitwise operators
Related: Hash Sets vs Maps