Every number appears twice except two. XOR everything to get a XOR b, take its lowest set bit to split the numbers into two lanes, and XOR each lane to find the two loners, in O(n) time and O(1) space.
▼The problem
LeetCode 260 (Medium). In nums every element appears exactly twice except two elements that appear once; return those two, in any order, in O(n) time and O(1) extra space.
Examples (LeetCode's): [1,2,1,3,2,5] → [3,5] (the walkthrough example); [-1,0] → [-1,0]; [0,1] → [1,0] (both checked, not shown).
The solution
def singleNumber(nums):
x = 0
for n in nums:
x ^= n
low = x & -x
a = b = 0
for n in nums:
if n & low:
a ^= n
else:
b ^= n
return [a, b]Transcript
Single Number Three. Every number appears twice, except two that appear just once. Find those two, in linear time and constant extra space.
Take one, two, one, three, two, five. The ones pair up, and so do the twos. The loners are three and five.
The easy way counts each number in a hash map. That's linear time, but the map grows with the list.
Recall from Single Number: XOR cancels a number with its twin. So XOR everything. The pairs vanish, and what's left is three XOR five: zero, one, one against one, zero, one gives one, one, zero. That's six.
Six isn't zero, so three and five differ in at least one bit. Take the lowest one: x AND negative x keeps only that bit, here two. Now send every number down one of two lanes by that bit. Twins share every bit, so they always land together, but three and five must split up.
In code, XOR all the numbers into x. Keep its lowest set bit. Loop again: numbers with that bit go into a, the rest into b. Return a and b.
Let's run it with the bit two. One has no two bit: lane b. Two: lane a. One: lane b. Three: lane a. Two: lane a. Five: lane b. Lane a holds two, three, two: that leaves three. Lane b holds one, one, five: that leaves five.
Two passes over the list: linear time. Just x, the bit and two totals: constant space.
XOR everything, split on a bit where they differ, XOR each lane. That's Single Number Three.