Two Lone Values
Problem
In a list of integers, every value appears exactly twice except two different values that appear once each. Return those two, smaller first. Use linear time and constant extra space, so a tally of every value is not allowed.
Examples
Input: nums = [1, 2, 1, 3, 2, 5]
Output: [3, 5]Input: nums = [2, 0, 2, 6]
Output: [0, 6]
Why: zero can be one of the lone valuesInput: nums = [4, 9]
Output: [4, 9]
Why: edge case, no pairs at all, only the two lone valuesHints
0 / 3
XOR of the whole list cancels every pair, but here it leaves the two lone values mixed together into one number.
That mixed number is not zero, because the two lone values differ. Any one bit in it marks a position where the two lone values disagree.
Pick one set bit of the combined XOR, for example the lowest. Split the list by whether each value has that bit. Each pair lands entirely on one side, and the two lone values land on opposite sides, so XOR-ing one side alone recovers one lone value; XOR it with the combined value to get the other.
Solution
XOR-ing everything leaves a XOR b, since each pair cancels itself. Because a and b differ, that result has at least one set bit, and at that position exactly one of them has a one. Splitting the whole list on that bit sends both copies of every pair to the same side while separating a from b, so XOR-ing one side isolates one lone value, and XOR-ing it back into the combined result gives the other. The lowest set bit is found with x AND negative x. Time is O(n) over two passes and space is O(1).
def two_lone(nums):
both = 0
for x in nums:
both ^= x # pairs cancel, leaving a ^ b
low = both & -both # a bit where a and b disagree
a = 0
for x in nums:
if x & low: # one side of the split; pairs never straddle it
a ^= x
b = both ^ a
return [min(a, b), max(a, b)]
print(two_lone([1, 2, 1, 3, 2, 5])) # -> [3, 5]
print(two_lone([2, 0, 2, 6])) # -> [0, 6]
print(two_lone([4, 9])) # -> [4, 9]Stuck on the idea rather than the code? XOR Tricks covers it.