Single Number looks like it needs a hash map, and that solution works. But there is a slicker trick that uses O(1) space and one of the most elegant properties in all of bit manipulation: XOR.
Problem. Given a non-empty array nums where every element appears twice except for one
element that appears once, find that single element. You must do it with linear time and
constant extra space.
Example: nums = [4, 1, 2, 1, 2] → answer 4 (every other value shows up twice).
The slow way first
The obvious idea: count how many times each value appears with a hash map, then return the one whose count is 1. That runs in O(n) time, but it uses O(n) extra space for the map — and the problem explicitly asks for constant space.
The question to ask: is there a way to make duplicates erase themselves so I never need to store them? There is — and it comes from how XOR behaves on pairs.
The idea: XOR cancels pairs
XOR (^) has three properties that combine beautifully here:
x ^ x = 0— a value XOR-ed with itself cancels to zero.x ^ 0 = x— XOR-ing with zero changes nothing.- XOR is commutative and associative — order does not matter.
So if we XOR every number in the array into a single accumulator, each value that appears twice cancels itself to 0, and the lone value (XOR-ed with a pile of zeros) survives.
The key insight: we never need to know which numbers are duplicates. The math sorts that out for us — every pair quietly deletes itself.
Walk through it
Step through the animation. The pointer i scans left to right while the result cell shows the running XOR. Watch the value bounce around as new numbers mix in, then collapse back down as each duplicate cancels its earlier copy. After the last element, only 4 is left.
Pseudocode
set result = 0
for each num in nums:
result = result XOR num # pairs cancel, unique value accumulates
return result # the one number that appeared onceThe Python solution
def single_number(nums):
result = 0
for num in nums:
result ^= num
return resultresultstarts at0, the identity for XOR (XOR-ing anything with 0 leaves it unchanged).- The loop folds every number into
resultwith the in-place XOR operator^=. - Line 4 is the whole trick: each value that appears twice cancels itself to 0 across the loop.
- Because order does not matter for XOR, we can process the array in a single straight pass.
- Whatever survives is the number that appeared an odd number of times — here, exactly once.
Complexity
| Case | Time | Notes |
|---|---|---|
| Hash-map counting | O(n) (moderate) | needs O(n) extra space |
| XOR accumulator (this solution) | O(n) (moderate) | one pass, no extra storage |
O(1) (fast)Both solutions are O(n) time, but the XOR version uses only a single integer — O(1) space. That is exactly what the problem demands, and it is what makes this answer stand out in an interview.
When this pattern shows up
When a problem talks about elements appearing in pairs (or any even count) with one odd one out, think XOR. It is the cleanest way to cancel duplicates without a hash set. Variants include finding a missing number or detecting the single non-repeating element.
XOR only rescues the value that appears an odd number of times. If a value appeared three times, or if there were two unique values, plain XOR would not isolate a single answer — those are different problems needing a different trick.
Practice
For nums = [4, 1, 2, 1, 2], what is result right before the final element is processed, and what is it after?
1. Why does XOR-ing all the numbers leave only the unique one?
2. Why do we initialize result to 0?
3. What is the extra space used by the XOR solution?
4. Does the order in which we process the numbers matter?