Every number appears three times, except one that appears once. Find it in linear time and constant space.
DSA Animator › DSA Revision › Bit Manipulation › Single Number II
Remember: count bits per position, mod the repeat count. The same trick works for any repeat count k. The video solves Single Number II (LeetCode 137, Medium) with the Bit Counting mod 3 pattern from the Bit Manipulation topic, and you can replay every step in the interactive Single Number II animation.
Every number appears three times, except one that appears once. Find it in linear time and constant space.
For 2, 2, 3, 2, the answer is 3.
XOR does not work here, because three copies do not cancel. A hash map works, but it uses extra space.
Look at each bit position separately. Count how many numbers have a 1 in that position. Numbers appearing three times add a multiple of 3 to that count. So the count mod 3 is exactly the bit of the single number.
In binary, 2 is 10 and 3 is 11. For bit 0, only the 3 has a 1, so the count is 1, and 1 mod 3 is 1. For bit 1, all four numbers have a 1, so the count is 4. 4 mod 3 is 1, so bit 1 is also set. The bits are 11, which is 3.
In code, loop over the 32 bit positions. For each, count the numbers with that bit set. If the count mod 3 is not 0, set that bit in the result. It's O of 32 times n, which is linear.
Remember: count bits per position, mod the repeat count. The same trick works for any repeat count k.