Total Hamming Distance: Counting Bits Column by Column

LeetCode Total Hamming Distance (Problem 477) gives you an array of integers and asks you to find the sum of Hamming distances between all pairs. Given nums, return the total Hamming distance across every pair (nums[i], nums[j]) where i is less than j.

For example, nums = [4, 14, 2]. The pairwise Hamming distances are: dist(4,14) = 2, dist(4,2) = 2, dist(14,2) = 2. The total is 6.

The problem

You could compute every pairwise Hamming distance using XOR and popcount, but that takes O(n^2) time. With n up to 10,000 numbers, you need something faster. The trick is to stop thinking about pairs and start thinking about individual bit positions.

Why this problem matters

This problem teaches you to decompose a global counting question into independent per-bit subproblems. That column-by-column perspective is a recurring theme in bit manipulation. Once you see it, you can apply the same reasoning to problems like Bitwise AND of Numbers Range and Counting Bits.

The insight also shows the power of combinatorics inside algorithms. Instead of iterating over all pairs and checking each bit, you count how many numbers have a 1 at each position and how many have a 0. The number of pairs that differ at that position is simply ones * zeros. That single multiplication replaces what would otherwise be a nested loop.

The key insight

For any single bit position, look at the entire array and count how many numbers have a 1 at that position (ones) and how many have a 0 (zeros). Every pair where one number has a 1 and the other has a 0 at that position contributes 1 to the total Hamming distance. The number of such pairs is ones * zeros.

Why? If there are ones numbers with a 1 and zeros numbers with a 0, you can form ones * zeros pairs that differ at that bit. This is basic combinatorics: pick one from the "ones" group and one from the "zeros" group.

Since bit positions are independent, you just sum up the contributions across all 32 bit positions (or however many bits your integers use). That gives you the total Hamming distance in O(32 * n) = O(n) time.

The code

def totalHammingDistance(nums):
    total = 0
    for bit in range(32):
        ones = sum(1 for n in nums if n & (1 << bit))
        zeros = len(nums) - ones
        total += ones * zeros
    return total

For each of the 32 bit positions, you count how many numbers have a 1 at that position. The rest have a 0. Multiply, add to the running total, and move to the next bit. That is the entire algorithm.

Here is a slightly more compact version:

def totalHammingDistance(nums):
    total = 0
    for bit in range(32):
        ones = sum((n >> bit) & 1 for n in nums)
        total += ones * (len(nums) - ones)
    return total

Both do the same work. Shifting right by bit positions and masking with 1 isolates the bit at position bit.

Step-by-step walkthrough

Let's trace through nums = [4, 14, 2] bit by bit. In binary: 4 is 0100, 14 is 1110, and 2 is 0010. Watch how each bit position contributes independently.

Adding up the contributions: 0 + 2 + 2 + 2 = 6. That matches the sum of all pairwise Hamming distances.

Complexity analysis

You iterate over 32 bit positions, and for each one you scan the array once. The constant factor of 32 comes from the integer width. No extra data structures are needed beyond a few counters.

Compare this to the brute-force approach of checking all pairs: that would be O(n^2 * 32), which is far too slow for large inputs.

Building blocks

Bit isolation with masking. (n >> bit) & 1 extracts the value of a single bit at a given position. You shift the target bit to the rightmost position, then mask off everything else with & 1. This is the same primitive used in Number of 1 Bits and Counting Bits.

Column-wise decomposition. Instead of processing pairs of numbers, you process columns of bits. Each column (bit position) is independent, so you can count contributions separately and sum them. This "decompose by bit position" strategy appears in many problems where you need aggregate statistics across all pairs.

Combinatorial counting. If ones numbers have a 1 and zeros numbers have a 0 at some bit position, the number of differing pairs is ones * zeros. This avoids explicitly enumerating pairs. The same counting trick appears whenever you need to count pairs with a particular property across a set.

Edge cases

All numbers identical: If every number in the array is the same, then at every bit position either all have 1 or all have 0. That means ones * zeros = 0 at every position. The total Hamming distance is 0, which is correct since identical numbers have Hamming distance 0.

Single element: If the array has only one number, there are no pairs. The loop still runs, but ones * zeros can never exceed 0 in a meaningful way. Actually, with n = 1, either ones = 1, zeros = 0 or ones = 0, zeros = 1, so the product is always 0. Correct.

All bits set vs all bits zero: Consider nums = [0, 2147483647]. The maximum 31-bit integer has all bits set. Every bit position has one 1 and one 0, so the contribution per bit is 1. The total is 31.

Large arrays: With n = 10,000, the brute force would need roughly 50 million pair comparisons. The column-wise approach does 32 * 10,000 = 320,000 operations. That is a 150x speedup.

From understanding to recall

The mental model is: "process bits column by column, not pair by pair." For each column, count ones and zeros, multiply them, add to the total. That is the whole algorithm.

The recall anchor: "ones times zeros per bit position." If that phrase comes to mind when you see this problem, the code writes itself. You loop over 32 bits, count how many numbers have a 1, compute the contribution, and sum.

Practice this cold a few times. The implementation is short enough that you should be able to write it in under two minutes after a few reps. The real skill is recognizing when the column-by-column decomposition applies, and that recognition comes from repetition.

Related posts

• Hamming Distance - The single-pair version of this problem. Understanding XOR and popcount for two numbers is the prerequisite for the column-wise generalization here.
• Number of 1 Bits - Counting set bits in a single number. The bit isolation technique (n >> bit) & 1 is the same primitive used in Total Hamming Distance.
• Counting Bits - Builds a popcount table for all numbers from 0 to n. Another problem where per-bit reasoning unlocks an efficient solution.