1265. Appearing Once While Everything Else Appears Three Times

Every value in an array appears exactly three times, except one which appears once. Print that value.

2 2 3 2 -> 3 5 5 5 1 2 2 2 -> 1 7 7 7 0 -> 0

## What most people try first

XOR everything, as in #1247. It does not work and understanding WHY is the whole problem. XOR cancels pairs, so it kills anything appearing an EVEN number of times. Three is odd: v ^ v ^ v = v. So XORing the array gives the XOR of every distinct value, the survivor included, with nothing cancelled at all. On 2 2 3 2 it gives 2 ^ 2 ^ 3 ^ 2 = 3, which happens to be right, and on 5 5 5 1 2 2 2 it gives 5 ^ 1 ^ 2 = 6, which is not. Coincidence on the first input is exactly how this bug ships.

A hash map works and costs O(n) space. Sorting works and costs a sort. The question asks for O(1) extra space and one pass.

## XOR is parity, and parity is the wrong modulus

The reason XOR works for duplicates is that at each bit position it keeps the count of ones MODULO 2. Pairs vanish because 2 is 0 mod 2. Triples do not vanish because 3 is 1 mod 2.

So the fix is to change the modulus. Count, at each bit position independently, how many of the n values have that bit set, and take the count modulo 3. Every tripled value contributes 3 to each position where it has a bit, which is 0 mod 3 and disappears. The survivor contributes 1 to each of its own positions and 0 elsewhere. So

for each bit position p: c = how many values have bit p set if c mod 3 != 0: the answer has bit p set

reconstructs the survivor one bit at a time, and the reconstruction is exact rather than probable: the count mod 3 at position p is 1 exactly when the survivor has a 1 there.

## Why this is the general shape

The pattern is "accumulate per bit position modulo however many times the duplicates appear". With duplicates appearing twice, modulo 2 is XOR and the whole thing collapses into one operation, which is why #1247 looks like magic rather than like counting. With three, or five, or any k, the counting version is what remains, and it is the version worth remembering because it does not depend on k being 2.

## Cost

O(30 n) time, which at n = 200000 is six million bit tests, and O(1) space: 30 counters, or a single accumulator if you prefer the two-variable trick. There is a well-known three-line version using two accumulators called ones and twos; it is the same arithmetic modulo 3 done in parallel across all positions, and it is much harder to be sure of. The per-position count is the version to write first and the one the reference solutions use.

## Width

Values are at most 1073741823, which is 2^30 - 1, so only positions 0 through 29 can ever be set and the loop runs over 30 positions. Every value and the reconstructed answer fit in a signed 32-bit integer, whose limit is 2147483647. The per-position counts reach n = 200000 at most and also fit in 32 bits.

JavaScript is safe here with plain Numbers: >>, & and | all coerce to signed 32 bits, and every quantity involved already fits in signed 32 bits. Note that this would stop being true at a bound of 2^31, because 1 << 31 in JavaScript is -2147483648, and the same expression overflows a signed 32-bit int in C, C++ and Java. The bound is 2^30 - 1 so that position 30 is never needed and that whole hazard, which #1297 is about, does not arise.

Constraints - `1 ≤ n ≤ 200000`, and `n` leaves remainder 1 when divided by 3 - `0 ≤ a[i] ≤ 1073741823` - exactly one value appears once and every other value appears exactly three times