#136
Single Number
Easy XOR
- Read
- Understand
- Hints
- Approach
- Solution
- Solved
?The problem
Every number appears twice except one. Find that one in linear time and constant extra space.
This is a short summary in our own words. Read the full statement and examples on LeetCode: open problem ↗
◎Understanding
Really asking: everything comes in pairs except one; find the loner.
Why this works: x ^ x = 0 and x ^ 0 = x, and order doesn't matter, so XOR of everything cancels the pairs.
Example: [4, 1, 2, 1, 2]
0^4 = 44^1 = 5, 5^2 = 77^1 = 6, 6^2 = 4 → answer 4
✦Hints open one at a time
What is a ^ a? What is a ^ 0?
XOR is order-independent, so pairs cancel no matter where they are.
↗Approach
XOR all numbers together. Every pair becomes 0 and the single number is left.
</>Solution (Java)
class Solution {
public int singleNumber(int[] nums) {
int x = 0;
for (int v : nums) x ^= v; // pairs cancel out
return x;
}
}!Common mistake
Reaching for a HashMap — it works but uses O(n) space, which the problem asks you to avoid.
Complexity
- Time: O(n).
- Space: O(1).
