Single Number III
Find the two elements that appear exactly once when every other element appears twice, with XOR and a split on one differing bit, in linear time and constant space.
Problem Understanding
Single Number III: in nums, exactly two elements appear once and every other element appears exactly twice. Return the two, in any order, using linear time and constant extra space.
Examples: [1,2,1,3,2,5] → [3,5]; [-1,0] → [-1,0]; [0,1] → [1,0].
The Intuition: Turn One Problem Into Two Single Numbers
Single Number finds one unpaired value with XOR. With two of them, XOR only gives x ^ y. The trick is to split the array so each half has exactly one:
- XOR everything:
diff = x ^ y. - Find a differing bit:
diff & -diff. - Split by that bit and XOR each group: pairs stay together, x and y separate.
For values that appear three times instead, see Single Number II.
Interactive Walkthrough
LOW 6 BITS · AMBER = THE SPLITTING BIT
diff = 0
1
2
1
3
2
5
diff
diff
0
group 1
:
group 0
:
diff = 0. XOR every number into it: each pair cancels, leaving x ^ y
Next
diff ^= 1: 000001 (1)
nums
Each number is a row of bits. After diff is built, its lowest 1 bit marks a column, and every number is tagged with the group it falls into. Try High bit to see a split on a bit other than bit 0.
Dry Run Table
Input: [1,2,1,3,2,5].
| Step | Value |
|---|---|
| diff = 1^2^1^3^2^5 | 3 ^ 5 = 6 (110) |
| low = diff & -diff | 2 (010) |
| bit 1 set: 2, 3, 2 | 2 ^ 3 ^ 2 = 3 |
| bit 1 clear: 1, 1, 5 | 1 ^ 1 ^ 5 = 5 |
Answer: [3,5].
The Solution Template
Two passes of XOR.
Single Number III Code
1var singleNumber = function(nums) {2 let diff = 0;3 for (const num of nums) diff ^= num;4 const low = diff & -diff;5 let a = 0, b = 0;6 for (const num of nums) {7 if (num & low) a ^= num;8 else b ^= num;9 }10 return [a, b];11};
Edge Cases & Common Mistakes
- One of the singles is 0: fine; 0 goes to the group without the bit.
- Negative numbers: bits work the same in two's complement.
- INT_MIN overflow in C/C++: negate as unsigned.
- Using a hash map: correct, but O(n) space.
- Order of the answer: any order is accepted.
Summary
XOR everything to get x ^ y, take its lowest set bit, and XOR the numbers in each half of the split. O(n) time, O(1) space.
More practice: DSA interview questions with answers · patterns cheat sheet