The one number that is not repeated three times

Every number in the list appears exactly three times, except one, which appears once. Find that one. Use constant extra memory.

Worked example#

For [2, 2, 3, 2] the answer is 3: the twos appear three times, the three appears once.

For [0, 1, 0, 1, 0, 1, 99] the answer is 99.

Why the usual trick fails#

For pairs there is a beautiful one-liner: exclusive-or everything together. Equal values cancel, so the odd one out survives.

That works because x ^ x = 0: two copies vanish. Three copies do not. x ^ x ^ x = x, so the trick leaves every value behind and tells you nothing.

Thinking in columns#

Look at one bit position at a time, across all the numbers.

Every number that appears three times contributes either zero or three to that column's count of ones. So the total count in each column is a multiple of three, plus whatever the lonely number contributes there.

So take the count modulo three. What is left is exactly the lonely number's bit. Do that for all 32 columns and you have rebuilt it.

That is the version to write first: it is obvious, it uses a fixed 32 counters, and it is easy to argue is correct. Watch the sign bit if your language has signed integers.

Counting to three with two bits#

There is a tighter version that does the same thing in one pass with two variables.

Keep ones and twos, where a bit set in ones means that column has seen the value once so far, and in twos means twice. When a column reaches three, both are cleared, which is the modulo-three happening in place:

ones = (ones ^ value) & ~twos
twos = (twos ^ value) & ~ones

Together the two variables are a counter that goes 0, 1, 2, 0 in every column at once. At the end, ones holds the answer.

It is worth deriving this on paper once and then not memorising it. The column-counting version is the one to reach for under pressure, because you can rebuild it from the idea.

Constraints#

• 1 <= n <= 30000, with exactly one value appearing once and all others three times
• values fit in a signed 32-bit integer