LeetCode 477 · Bits · Math

Total Hamming Distance, explained with a picture

All pairs of panels, one column at a time.

Bits · Math
▶ Watch it step by step

The problem

Sum the Hamming distances over every pair of numbers in the list.

Input:  [4, 14, 2]
Output: 6

Picture it

Picture all the panels stacked. Look at one switch column at a time: if k panels have it on and n − k have it off, that column adds k × (n − k) to the total, since every on/off pair differs there.

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 counting instead of per-pair comparison. O(32n).

Python solution

def total_hamming(nums):
    total = 0
    for bit in range(32):
        ones = sum((x >> bit) & 1 for x in nums)
        total += ones * (len(nums) - ones)   # on/off pairs in this column
    return total

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.