Every value in an array appears exactly twice except two values that appear once. Give an O(n) time O(1) space algorithm to find both, and state precisely the input assumption that makes it work and what it returns when that assumption fails.

Every value in an array appears exactly twice except two values that appear once. Give an O(n) time O(1) space algorithm to find both, and state precisely the input assumption that makes it work and what it returns when that assumption fails.

Approach: The XOR of everything cancels the pairs. Use one set bit of the result to split the array into two groups that each contain one of the answers.

XOR everything to get x = a xor b, isolate any set bit with x AND -x, partition by that bit and XOR each part. The XOR of the whole array cancels every value appearing twice and leaves a xor b, which is non-zero because a and b differ. Take the lowest set bit b0 = x AND -x, a two's complement identity that leaves exactly the least significant one bit. That bit differs between a and b by construction, so partitioning the array on whether a value has b0 set puts a in one group and b in the other, while every duplicated pair lands together in the same group. XOR each group separately and the two results are a and b. Two passes, no extra memory beyond three registers. The assumption is that exactly two values occur an odd number of times and every other value occurs an even number of times, since XOR only sees parity. If three values are unique the method returns the XOR of some subset of them and gives no error, and if a value appears four times it is invisible to the algorithm, so the result is silently wrong rather than detectably wrong.

Follow-up: How do you find the one value appearing once when every other value appears exactly three times, still in O(1) space?

Key concepts: xor, lowest set bit, partition, parity assumption.