LeetCode 137 · Bits · Math

Single Number II, explained with a picture

Triplets and one loner, counted switch by switch.

Bits · Math
▶ Watch it step by step

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 result

In the interactive version each line lights up as the animation runs, and you can type your own input to see the algorithm handle it.