The problem
Every number appears three times except one. Find that one.
Input: [2, 2, 3, 2] Output: 3
Picture it
Picture each number as a switch panel. Look at one switch position at a time and count how many numbers have it on. Triplets add a multiple of 3 to every position, so “count mod 3” leaves exactly the loner’s switch.
Short version: the full lesson (brute force, complexity, edge cases and a quiz) is still being written. The animation is complete.
The key idea
Per-bit count mod 3 (or the ones/twos bitmask trick). O(32n).
Python solution
def single_number(nums): # every value 3 times but one
result = 0
for bit in range(32):
total = sum((x >> bit) & 1 for x in nums)
if total % 3:
result |= 1 << bit
return resultIn the interactive version each line lights up as the animation runs, and you can type your own input to see the algorithm handle it.