Total Hamming Distance
Total Hamming Distance: given an integer array nums, return the sum of Hamming distances between all pairs of numbers.
- 1 <= nums.length <= 10⁴
- 0 <= nums[i] <= 10⁹
- The answer for the given input will fit in a 32-bit integer.
Intuition
Total hamming distance sums the Hamming distance over every pair of numbers in an array. With n numbers there are n(n−1)/2 pairs, so computing each pair's distance is O(n²) and too slow.
The reframing that fixes it changes what is iterated over:
- Instead of summing over pairs, sum over bit positions — for each of the 32 positions, count how many numbers have a 1 there.
At a given position, a pair contributes 1 to the distance exactly when one number has a 1 and the other a 0. If c numbers have a 1, then n − c have a 0, and the number of such pairs is c × (n − c).
Summing that product across all 32 positions gives the total, because Hamming distance is defined bit by bit and the positions are independent.
That independence is the whole insight. Each bit position can be handled in isolation and the results simply added — no pair is ever examined directly.
The cost becomes O(32n), which is O(n) for fixed-width integers.
The common error is computing c × (n − c) inside the loop over numbers rather than after counting them all. The product depends on the final count, so it must be applied once per bit position, after that position's tally is complete.
Extracting bit i from a number is (num >> i) & 1, looped over all 32 positions.
No modulus is needed — the constraints keep the result within 32-bit range, though using a wider accumulator is harmless.
The approach generalises: whenever a pairwise sum decomposes into independent components, counting per component beats enumerating pairs.
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
Before reading on: price up what the direct approach costs here, then ask which operator makes the unwanted values cancel themselves out. Aim for O(30n) = O(n) time and O(1) space.
Iterate bits, not pairs
Sum over the 32 bit positions rather than over pairs. Hamming distance is defined bit by bit, and the positions are fully independent.
Count ones per position
For each bit position, count how many numbers have a 1 there using (num >> i) & 1. That single count determines the position's contribution.
Multiply ones by zeros
With c ones and n − c zeros, exactly c × (n − c) pairs differ at that position — one number with a 1, the other with a 0.
Apply the product after counting
Compute c × (n − c) once the position's tally is complete, not inside the loop over numbers — the product depends on the final count.
Sum across all positions
Add each position's contribution. Independence between bits is what makes simple addition correct here.
Cost of the approach
32 positions each scanning n numbers gives O(32n) time — linear for fixed-width integers — with O(1) space.
Solution & live demo
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.