Single Number III
Medium XOR + lowest set bit
- Read
- Understand
- Hints
- Approach
- Solution
- Solved
?The problem
Every number appears twice except two different numbers that appear once each. Return those two.
This is a short summary in our own words. Read the full statement and examples on LeetCode: open problem ↗
◎Understanding
Really asking: two different loners, everything else in pairs.
Why this works: XOR of all = a ^ b, which has a 1 where a and b differ. Split all numbers by that bit; each group becomes the easy "single number" problem.
Example: [1, 2, 1, 3, 2, 5]
xor = 3 ^ 5 = 110lowest bit = 010group with bit: 2, 3, 2 → 3group without: 1, 1, 5 → 5
✦Hints open one at a time
↗Approach
x = XOR of all. Pick its lowest set bit with x & -x. Numbers with that bit set go to group A, the rest to B. Pairs land in the same group and cancel, leaving a in one group and b in the other.
</>Solution (Java)
class Solution {
public int[] singleNumber(int[] nums) {
int xor = 0;
for (int v : nums) xor ^= v;
int bit = xor & -xor; // lowest bit where the two answers differ
int a = 0, b = 0;
for (int v : nums) {
if ((v & bit) != 0) a ^= v;
else b ^= v;
}
return new int[]{a, b};
}
}!Common mistake
Using x & (x - 1) to pick the bit — that clears the lowest set bit instead of isolating it. Use x & -x.
- Time: O(n).
- Space: O(1).
