1264. The Two Values That Appear Only Once

Every value in an array appears exactly twice, except TWO values which each appear once. Print those two in increasing order.

1 2 1 3 2 5 -> 3 5 4 4 5 5 6 6 1 2 -> 1 2 0 1 -> 0 1

## What most people try first

Problem 1247 does the one-survivor version: XOR everything and the single unpaired value falls out. The reflex here is to do the same and hope. XORing everything gives A ^ B, the two survivors mixed together, and no amount of further work on that one number separates them, because the map (A, B) -> A ^ B is not injective: (1, 2) and (5, 6) both give 3.

A sort, or a hash map, solves it in O(n log n) time or O(n) space. The point of the problem is to do it in one accumulator pair and no extra memory.

## One accumulator isolates one survivor

That is the real lesson. A single XOR total cancels everything that appears an even number of times, so it can tell you about the odd-count values only as a lump. To get two answers you need two independent accumulators, and the question becomes how to send each survivor to a different one.

## A bit where they disagree

Let x = A ^ B, which is what XORing the whole array gives. x != 0, because A != B. Take its lowest set bit:

b = x & -x

A set bit in A ^ B means exactly that A and B differ at that position. So one of them has bit b set and the other does not, guaranteed.

Now XOR the array again, routing each value by that bit:

for v in a: if v & b: g1 ^= v else: g2 ^= v

Every PAIRED value still cancels, because its two copies are the same number, so they share bit b and go to the same accumulator. A and B go to different ones. Therefore g1 and g2 end up holding the two answers, one each, and the array never had to be stored or sorted.

Any set bit of x works. The lowest is chosen because x & -x finds it in one operation, as #1250 argues.

## Why the output order is specified

The two accumulators give the answers in whichever order the bit routing happened to put them, which is not meaningful. The problem therefore asks for increasing order, so the answer is well defined and a correct solution does not depend on which accumulator got which. Sorting two numbers is one comparison.

## Width

Values are at most 1073741823, which is 2^30 - 1, so every value and every XOR of values stays below 2^30 and never reaches bit 31. Everything fits in a signed 32-bit integer, whose limit is 2147483647, and JavaScript's ^ and & on plain Numbers are therefore safe: the coercion to signed 32 bits cannot alter a value that already fits. Had the bound been 2^31 or higher, x & -x in JavaScript would have returned a negative number and the routing would have inverted, which is why the bound is stated as a power of two rather than as a round decimal.

Constraints - `2 ≤ n ≤ 200000`, and `n` is even - `0 ≤ a[i] ≤ 1073741823` - exactly two values appear once and every other value appears exactly twice