Single Number II
Every element of nums appears exactly three times except for one, which appears once. Return that single element in linear time and constant extra space.
Intuition
XOR solved the two-copies version because a ^ a = 0 — pairs erase themselves. Three copies do not erase, so the whole trick collapses and we need a different cancellation. Drop a level of abstraction and look at a single bit column across all the numbers. A value appearing three times contributes either three ones or zero ones to that column — in both cases a multiple of three. So the count of ones in each column, taken modulo 3, is exactly what the single number contributes there. Rebuild the answer column by column.
XOR can't help when values repeat three times, so count each bit position independently. Bits belonging to tripled numbers occur a multiple of 3 times; whatever remains modulo 3 belongs to the single value. Per-bit counting generalises to any repeat count.
Approach
Start with the hash map so you know what you are replacing
The obvious solution counts frequencies in a map and returns the key whose count is 1. It is O(n) time, which is already optimal — but it costs O(n/3) space, and that space is the entire point of the problem. Knowing this baseline matters in an interview: state it, give its complexity, then say why the interviewer will push back on it.
Look at one bit column instead of one number
Write every value in binary and stack them. Take the numbers [5,5,5,2,4,4,4]. In binary: 101, 101, 101, 010, 100, 100, 100. Now read down the rightmost column: three ones, all from the fives. The next column: exactly one one, from the two. The next: six ones, three from the fives and three from the fours. Every column's count is a multiple of three, plus whatever the lone number puts there. That is a cancellation rule that survives triples, which is exactly what XOR could not give us.
Take each column count mod 3 and reassemble
For each of the 32 bit positions, count how many numbers have that bit set. If count % 3 is 1, the single number has that bit set, so OR 1 << i into the answer; if it is 0, the single number does not. Thirty-two passes over the array is O(32n) = O(n) with O(1) space. In a language with signed 32-bit ints, handle bit 31 by treating the assembled value as a signed integer — in Python that means subtracting 1 << 32 when bit 31 comes out set.
Solution & live demo
Common pitfalls
Using XOR
for n in nums: ans ^= n
if count % 3:
ans |= (1 << i)XOR annihilates pairs, but three copies of a value leave one copy behind, which mixes into the result. Only counting modulo the repeat factor isolates the single.
Not sign-correcting the result
return ans
if ans >= (1 << 31):
ans -= (1 << 32)
return ansPython integers are unbounded, so setting bit 31 produces a large positive number instead of a negative one. The manual two's-complement fix-up is needed for negative answers; C++ and Java get it for free from fixed-width ints.
Counting over the wrong bit width
for i in range(max(nums).bit_length()):
for i in range(32):
Negative inputs have high bits set that bit_length on the maximum never reaches, so those positions are never counted and the answer loses its sign information. Fixing the width at 32 covers the stated constraints.
Edge cases
In Python integers are unbounded, so bit 31 must be interpreted manually: if the reconstructed answer has bit 31 set, subtract 1 << 32 to recover the negative value. C++ and Java get this for free from the fixed-width int.
Every column count is a multiple of 3, so no bit is ever set and the answer is 0 — correct, not a failure to find anything.
Each column count is 0 or 1; count % 3 reproduces the bits of the only element exactly.