Total Hamming Distance — Per-Bit Counting Beats N-Squared Pair Comparison

Problem Statement#

The Hamming distance between two integers is the number of positions at which the corresponding bits are different. Given an integer array nums, return the sum of Hamming distances between all the pairs of the integers in nums.

Constraints:

• 1 <= nums.length <= 10^4
• 0 <= nums[i] <= 10^9
• The answer for the given input will fit in a 32-bit integer.

Example 1:

Input:  nums = [4, 14, 2]
Output: 6
Explanation:
  HammingDistance(4, 14)  = 2 (binary: 0100 vs 1110)
  HammingDistance(4, 2)   = 2 (binary: 0100 vs 0010)
  HammingDistance(14, 2)  = 2 (binary: 1110 vs 0010)
  Total = 2 + 2 + 2 = 6

Example 2:

Input:  nums = [4, 14, 4]
Output: 4

Example 3:

Input:  nums = [0, 0, 0]
Output: 0

Why This Problem Matters#

Total Hamming Distance is a textbook example of decomposing an O(n^2) pair-aggregation problem into independent O(n) bit-position contributions. Naive brute force computes popcount(a ^ b) for every pair — O(n^2) — which fails at n = 10^4. The per-bit trick converts the same answer into a sum of products, achieving linear time.

The technique applies far beyond Hamming distance: any pairwise function that decomposes additively across bits (XOR sum, OR sum, bitwise sum-of-pairs metrics in error correction) follows the same pattern. Companies like Google, Amazon, and Meta use this question to test whether a candidate can recognize and exploit independence across bit positions — a recurring theme in competitive programming and high-throughput computing.

The Core Insight#

The total Hamming distance sums popcount(a ^ b) over all pairs (a, b). This is the total number of differing bit positions across all C(n, 2) pairs.

Key observation: total differing-bit count = sum over each bit position of (number of pairs where that bit differs).

For a fixed bit position b, let ones_b = number of values in nums with bit b set, and zeros_b = n - ones_b. The number of pairs that differ at bit b is exactly ones_b * zeros_b — every "set" element pairs with every "clear" element.

Summing across all 32 bit positions:

total_distance = sum over b in 0..31 of (ones_b * (n - ones_b))

This is O(32 * n) = O(n) time, O(1) extra space. Each bit position is independent, so we can also count all positions in a single pass with 32 counters.

Visual Dry Run#

Input: nums = [4, 14, 2]

Binary representations (low 4 bits):

• 4 = 0100
• 14 = 1110
• 2 = 0010

Per-bit counts:

Total = 0 + 2 + 2 + 2 + 0 = 6.

Verify against brute force:

• d(4, 14) = popcount(0100 ^ 1110) = popcount(1010) = 2
• d(4, 2) = popcount(0100 ^ 0010) = popcount(0110) = 2
• d(14, 2) = popcount(1110 ^ 0010) = popcount(1100) = 2
• Sum = 6. Match!

Solution (Optimal)#

Python#

class Solution:
    def totalHammingDistance(self, nums: list[int]) -> int:
        # For each bit position, count the values with that bit set
        # Each "set" value pairs with each "clear" value to add 1 to the total
        total = 0
        n = len(nums)
        for bit in range(32):
            ones = sum((x >> bit) & 1 for x in nums)   # count set bits at position
            total += ones * (n - ones)                 # pairs of (set, clear)
        return total

JavaScript#

var totalHammingDistance = function(nums) {
    // Per-bit independence: count ones at each of 32 positions
    let total = 0;
    const n = nums.length;
    for (let bit = 0; bit < 32; bit++) {
        let ones = 0;
        for (const x of nums) {
            ones += (x >> bit) & 1;   // 1 if bit is set, else 0
        }
        // every set-bit element pairs with every clear-bit element
        total += ones * (n - ones);
    }
    return total;
};

Complexity: Time O(32 * n) = O(n), Space O(1).

Common Mistakes#

1. Implementing the brute-force O(n^2) pair loop. Computing popcount(a ^ b) for all pairs gives the right answer but TLEs at n = 10^4 (10^8 pair operations).

2. Counting only ones, forgetting to multiply by zeros. A common slip is total += ones instead of ones * (n - ones). The product captures the number of differing pairs.

3. Stopping the loop early at bit == 30 instead of 31. nums[i] can be up to 10^9 < 2^30, but constraints sometimes allow 2^31. Always loop the full 32 bits to be safe.

4. Using arithmetic right shift on signed values. In Java/JS, >> performs sign extension on negatives. Use >>> (logical shift) or guard against negatives.

5. Integer overflow. With n = 10^4, ones * (n - ones) can reach 2.5 * 10^7, and summed across 32 bits can reach about 8 * 10^8 — still in 32-bit range, but candidates handling larger inputs should switch to 64-bit accumulators.

Interview Tips#

• Open with the brute-force as a baseline to demonstrate problem comprehension, then optimize: "Brute force is O(n^2), but I notice each bit position contributes independently."
• Articulate why bit positions are independent: differing bits at position 5 are unrelated to differing bits at position 7, so the total is a sum of per-bit counts.
• Mention that for very large n, you can vectorize the inner loop with SIMD or NumPy; for small n, the brute force may even be faster due to constant overhead.
• If asked to extend to "find the pair with maximum Hamming distance", note the per-bit decomposition no longer applies — you'd need a different approach (e.g., trie of bits).

Follow-up Questions#

Q: How would you compute the Hamming distance between two strings of equal length? Compare character by character; popcount in bit operations is for integers. For DNA sequences, encode each character with 2 bits then XOR.

Q: Can you do better than O(32 * n)? Not asymptotically — you must read every input value at least once. But you can run all 32 bit-position counts in a single pass over nums using 32 counters, improving cache behavior.

Q: How would you adapt this to a streaming setting where nums arrives one element at a time? Maintain 32 running counters. For each new element, update all 32 bit counts. After every update, compute sum(ones[b] * (n - ones[b])) if needed.

Q: How does this relate to error-correcting codes? Hamming distance underpins linear block codes. The minimum Hamming distance of a code determines its error-detection and correction capabilities; algorithms like this are core to coding theory.

Key Takeaways#

• Decompose the pairwise sum into per-bit contributions: each bit position contributes ones * (n - ones) to the total.
• Bit positions are independent — the total is the sum of per-bit pair counts across 32 positions.
• This converts O(n^2) brute force into O(32 * n) = O(n), a typical FAANG interview optimization.
• The technique generalizes to any pairwise additive bit-decomposable metric (XOR sum, OR sum, etc.).
• Watch for signed shifts on negatives in fixed-width languages — use >>> in JavaScript.
• For streaming or vectorized contexts, maintain per-bit counters across the input pass.