Intuition
XOR of everything cancels the pairs and leaves x ^ y, where x and y are the two singletons. Any set bit of that XOR is a bit where x and y differ, so partition all numbers by that bit into two groups — each singleton lands in a different group, and XOR within each group recovers it.
Explanation
Step 1 — collapse the pairs
XOR is its own inverse, so every value that appears twice cancels to 0. XOR-ing the whole array leaves:
xorAll = x ^ y
where x and y are the two unique numbers. Since x != y, xorAll has at least one set bit.
Step 2 — isolate one differing bit
Take the lowest set bit: diff = xorAll & (-xorAll). At this bit position x and y disagree — one has it set, the other doesn't.
Step 3 — split and XOR
Partition the numbers into those with the diff bit set and those without. x and y fall into different groups; pairs still cancel within each group. XOR each group to recover one singleton each:
a = b = 0
for v in nums:
if v & diff: a ^= v
else: b ^= v
return [a, b]
Worked example
nums = [1, 2, 1, 3, 2, 5].
xorAll = 1^2^1^3^2^5 = 3 ^ 5 = 6(binary110).diff = 6 & -6 = 2(binary010).- Bit-2-set group:
2, 3, 2→ XOR =3. Other group:1, 1, 5→ XOR =5.
Answer: [3, 5].
Complexity
- Time: O(n).
- Space: O(1).
Implementation
class Solution {
public int[] singleNumberIII(int[] nums) {
int xorAll = 0;
for (int v : nums) xorAll ^= v;
int diff = xorAll & (-xorAll); // lowest set bit
int a = 0, b = 0;
for (int v : nums) {
if ((v & diff) != 0) a ^= v;
else b ^= v;
}
return new int[]{a, b};
}
}