Single Number
Find the one number that appears once when every other appears twice, in O(n) time and O(1) space with XOR.
Problem Understanding
Single Number: in a non-empty array, every element appears exactly twice except one, which appears once. Find that one, in linear time with only constant extra space.
Examples: [2, 2, 1] returns 1; [4, 1, 2, 1, 2] returns 4.
The Intuition: Pairs Cancel Under XOR
XOR has three properties that solve this problem by themselves:
x ^ x = 0: a value cancels its own copy.x ^ 0 = x: zero changes nothing.- Order does not matter:
a ^ b ^ a = b.
So XOR every value together. The two copies of each repeated value cancel no matter how far apart they are, and the value that appears once is all that is left. The same idea drives Missing Number.
Interactive Walkthrough
The array is scanned once. Beside it is the set of values seen an odd number of times so far: a value joins on its first copy and leaves on its second. At the end only the single number remains, and it equals result.
Dry Run Table
Input: nums = [4, 1, 2, 1, 2]
| num | result (binary) |
result |
|---|---|---|
| start | 000 | 0 |
| 4 | 100 | 4 |
| 1 | 101 | 5 |
| 2 | 111 | 7 |
| 1 | 110 | 6 |
| 2 | 100 | 4 |
The Solution Template
XOR every value into one running result.
Single Number Code
1var singleNumber = function(nums) {2 let result = 0;3 for (const num of nums) {4 result ^= num;5 }6 return result;7};
Edge Cases & Common Mistakes
- One element: the answer is that element.
- Negative numbers: XOR works on their two's-complement bits just the same.
- Sorting first: comparing neighbours after a sort works but costs O(n log n).
- Values appearing three times: plain XOR fails; see the bit-counting approach for Single Number II.
Summary
XOR every value: pairs cancel, order does not matter, and the value that appears once is the result. One pass, O(1) space.
More practice: DSA interview questions with answers · patterns cheat sheet