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.
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
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.