Total Hamming Distance
Given an integer array nums, return the sum of Hamming distances between all pairs of numbers.
Intuition
Computing the Hamming distance for every pair is O(n²) — too slow. The breakthrough is to think about each bit position independently. At bit position b, some numbers have a 1 and some have a 0. A pair contributes 1 to the total at this bit only when one number has a 1 and the other has a 0. If c numbers have a 1 at bit b, then n - c have a 0, and the contribution from this bit is c * (n - c). Sum that over all 30 (or 32) bit positions and you have the answer in O(30n).
When a problem asks for the sum of some pairwise quantity over all pairs, and computing each pair individually is O(n²), look for a way to decompose the contribution by some independent dimension — here, bit positions. If you can count how many items are 'on' and 'off' in each dimension, the product gives the pairwise contribution. This bit-counting trick applies to any Hamming-distance aggregate.
Approach
Process each bit position independently
Instead of comparing numbers pairwise, iterate over bit positions 0 through 29 (sufficient for values up to 10⁹). For each bit position, count how many numbers have that bit set to 1.
Count the contribution of each bit using combinatorics
At bit b, let ones be the count of numbers with bit b set. The count of numbers with bit b unset is n - ones. Every pair where one has the bit set and the other doesn't contributes 1 to the Hamming distance. There are ones * (n - ones) such pairs. Add this to the running total.
Sum across all bit positions for the final answer
The total Hamming distance is the sum of contributions from all 30 bit positions. Time is O(30n) = O(n). Space is O(1) — just a counter and a loop variable.
Solution
Common pitfalls
Iterating only up to 16 bits instead of 30
for b in range(16):
for b in range(30):
Values can be up to 10⁹, which needs 30 bits. Stopping at 16 bits misses the upper bits and undercounts the Hamming distance for large numbers.
Counting pairs as ones ones instead of ones (n - ones)
total += ones * ones
total += ones * (n - ones)
ones * ones counts pairs where both have the bit set — those pairs contribute 0 to the Hamming distance at this bit, not 1. The contribution comes from mixed pairs: one set, one unset.
Shifting the number instead of the mask, losing the original value
for b in range(30):
num >>= 1
if num & 1: ones += 1for b in range(30):
if num & (1 << b): ones += 1Shifting num inside the bit loop destroys the original value after the first iteration. If you reuse num across the outer loop (over numbers), subsequent bits see a modified value. Use a mask (1 << b) to test each bit without mutation.
Edge cases
At every bit position, either all are 1 or all are 0. ones * (n - ones) is 0 in both cases. Total is 0, which is correct.
No pairs exist. The formula gives ones * (1 - ones) which is 0 for any value of ones (0 or 1). Total is 0.
0 has no bits set, so it contributes n - ones pairs at each bit position — correct, since its Hamming distance from any number with that bit set is 1 for that bit.