Single Number III
Single Number III: exactly two elements of nums appear once; every other element appears twice. Return the two singles in any order, in linear time and constant extra space.
- 2 <= nums.length <= 3 * 10⁴
- -2³¹ <= nums[i] <= 2³¹ - 1
- Each integer in nums will appear twice, only two integers will appear once.
Intuition
Single number iii has exactly two elements appearing once while all others appear twice, and both must be returned. The constant-space requirement rules out a hash map.
XORing everything gives a ^ b, the XOR of the two unique values — but not either one individually. The problem is separating them, and the insight is about what that combined value tells you:
- Any bit set in a ^ b is a bit where a and b differ, so partitioning the array on that bit puts the two unique values in different groups.
Pick any set bit — the lowest is easiest, isolated with x & (−x). Then split every element by whether that bit is set.
Each group now contains exactly one unique value, with every duplicate pair landing together in the same group since identical values share all bits. So XORing each group independently yields a and b.
The elegance is that no actual partitioning is needed. Two accumulators suffice — XOR each element into one or the other based on the chosen bit, in a single pass.
The combined XOR is guaranteed non-zero, because a and b are distinct and must differ somewhere. That guarantee is what makes the bit selection always possible.
Using x & (−x) to isolate the lowest set bit relies on two's complement, and works in every language with fixed-width signed integers. Any set bit would do equally well.
The output order is unspecified, so returning the two values in either order is accepted.
Two passes give O(n) time and O(1) space.
XOR everything and you're left with a ^ b. Any set bit in that result is a position where a and b differ, so partitioning the array by that bit puts the two singles in different buckets — and each bucket is now an ordinary Single Number problem.
Approach
Before reading on: price up what enumerating every case costs here, then ask which operator makes the unwanted values cancel themselves out. Aim for O(n) time and O(1) space.
XOR everything first
The result is a ^ b, the XOR of the two unique values. It does not give either one alone, which is the problem to solve.
Find a differing bit
Any set bit in a ^ b is a position where the two values differ. That difference is what allows them to be separated.
Isolate the lowest set bit
Compute x & (-x) using two's complement. Any set bit works, but the lowest is the cheapest to extract.
Partition on that bit
Split elements by whether the bit is set. Duplicate pairs land together, since identical values share every bit, so each group holds one unique value.
Use two accumulators
No actual partitioning is needed — XOR each element into one of two running values based on the bit, in a single pass.
Rely on the non-zero guarantee
a and b are distinct, so a ^ b is never zero and a set bit always exists. That is what makes the selection always possible.
Cost of the approach
Two passes with two accumulators give O(n) time and O(1) space, meeting the constant-space requirement.
Solution & live demo
Common pitfalls
Picking a bit that isn't set in the XOR
low = 1
low = x & -x
The partition only separates a from b if they differ at the chosen bit. x & -x isolates the lowest set bit of the XOR, which is guaranteed to be a disagreement; an arbitrary bit may put both singles in the same bucket.
XOR-ing the whole array into one bucket
if n & low: a ^= n else: a ^= n
if n & low: a ^= n else: b ^= n
The point of the partition is that each bucket contains exactly one single plus complete pairs. Folding everything into one accumulator just recomputes a ^ b and loses the separation.
Sorting or counting frequencies
return [k for k, v in Counter(nums).items() if v == 1]
low = x & -x
That's O(n) space, and the problem asks for constant. The two-pass XOR partition uses three integers regardless of input size.
Edge cases
No pairs to cancel. x = 1 ^ 2 = 3, the rightmost set bit separates 1 from 2, and each bucket holds one number.
x & -x relies on two's-complement negation, which is how Python and C++ already represent negatives, so isolating the low bit works unchanged.
Fine — 0 contributes nothing to any XOR but still lands in the bucket where the chosen bit is clear, and emerges as that bucket's value.