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.
Intuition
XOR-ing everything works beautifully when there is one loner, but with two it leaves a ^ b — a blend of both answers rather than either one. The way out is to stop treating the array as one group. If we can split it into two halves such that a lands in one and b in the other, and every duplicate pair stays together, then a single XOR over each half recovers the two numbers. The blend a ^ b tells us how to make that split.
Approach
XOR everything and see what survives
Fold the whole array with XOR. All the paired values cancel, exactly as in Single Number I, so what remains is x = a ^ b where a and b are the two loners. For [2,7,3,4,7,2,6] the pairs (2,2) and (7,7) vanish, leaving 4 ^ 6 = 2. This is progress but not an answer — we have the two numbers mixed together and no obvious way to separate them.
Read the surviving bits as a separation rule
Because a and b are different, x = a ^ b cannot be zero — at least one bit is set. And a set bit in x means exactly one thing: a and b disagree at that position. That is precisely the wedge we need. Pick any set bit of x — conventionally the rightmost, isolated with x & -x — and use it as a test. Every number in the array either has that bit set or does not, and by construction a and b fall on opposite sides.
Partition on that bit and fold each side
Walk the array a second time. If a number has the chosen bit set, XOR it into bucket one; otherwise into bucket two. Duplicates are identical, so both copies of any pair always land in the same bucket and cancel there. a and b land in different buckets and each survives alone. The two bucket values are the answer. Two passes, two accumulators, no extra memory that scales with n.
Solution & live demo
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.