Problem Statement
Total Hamming Distance
First, what is Hamming distance? Take two numbers and write them in binary (just 0s and 1s). The Hamming distance is how many positions have different bits, one number has a 1 and the other has a 0. For example, 4 is 100 and 14 is 1110, and they differ in 2 places, so their Hamming distance is 2. This problem asks for the total Hamming distance added up over every possible pair of numbers in the array. The slow way is to compare each number with every other number, which is O(n squared) work (it grows with the square of how many numbers you have). The trick here is to flip the question around. Instead of looking at pairs, we look at one bit position at a time. At a single position, say the numbers split into k that have a 1 there and (n - k) that have a 0 there. Every 1-number paired with every 0-number gives exactly one difference at this position, so that bit contributes k times (n - k). We do this for each bit position and add it all up.
Signals to notice
Brute force first
Check every pair — O(n²).
The key insight
For each of 32 bits: count numbers with 1 (c). Contribution = c × (n-c). Sum all bits. O(32n).
Trace it on nums=[4,14,2] (binary: 4=0100, 14=1110, 2=0010, n=3)
bit 0 (val 1): bits = 0,0,0 -> ones=0, contrib=0*(3-0)=0, total=0 bit 1 (val 2): bits = 0,1,1 -> ones=2, contrib=2*(3-2)=2, total=2 bit 2 (val 4): bits = 1,1,0 -> ones=2, contrib=2*(3-2)=2, total=4 bit 3 (val 8): bits = 0,1,0 -> ones=1, contrib=1*(3-1)=2, total=6 bits 4..31: all bits 0 -> ones=0, contrib=0, total stays 6 return total = 6
What must stay true
Per-bit contribution = number of 1-0 pairs = c × (n-c).
Shape of the loop
total = 0
for bit in 0..31:
ones = count of nums where (num >> bit) & 1 == 1
total += ones * (n - ones)
return totalPseudocode only — the full worked solution lives in the Solution tab.
Easy way to go wrong
Computing per-pair — per-bit counting avoids quadratic work.