Total Hamming
distance

Sum the differing-bit count over all pairs

Hamming distance between two numbers = how many bit positions differ, which is exactly the set-bit count of a XOR b. The task is the sum of that over every unordered pair. For [4,14,2] the three pairwise distances are 2, 1, 3 → total 6. The obvious approach compares all n(n−1)/2 pairs — O(n²), too slow for large arrays.

Count bit by bit, not pair by pair

Hamming distance is additive across bit positions and positions don't interact, so the double sum can be reordered: instead of "for each pair, sum over bits," compute "for each bit, sum over pairs." At one fixed bit, every number shows a 0 or a 1. A pair differs there exactly when one side is a 1 and the other a 0.

It's Σpairs Σbits = Σbits Σpairs — the same total, counted in a smarter order.

Each bit splits into ones and zeros

Enter numbers and step bit by bit. The current column highlights: 1-cells teal, 0-cells terracotta. The meters show that column's ones, zeros, its ones × zeros contribution, and the running total. Every other column dims so you can see one handshake-count at a time. Click any column header to jump to it.

Try 7 7 7 (every column all-same → every contribution 0) or 0 7 (three columns of 1×1 → total 3). The grid shows only the bits actually used.

[4, 14, 2] one bit at a time

Total = 0 + 2 + 2 + 2 = 6 — and the three individual Hamming distances (4,14)=2, (4,2)=1, (14,2)=3 were never computed. Every differing bit of every pair got counted exactly once, in column order.

Two loops, but 31 is a constant

int totalHammingDistance(int[] nums) {
    int n = nums.length;
    long total = 0;
    for (int bit = 0; bit < 31; bit++) {
        int ones = 0;
        for (int num : nums)
            ones += (num >> bit) & 1;        // count 1s in this column
        total += (long) ones * (n - ones);  // ones × zeros
    }
    return (int) total;
}

O(31·n) = O(n) time, O(1) space. A one-pass variant tallies an int[31] of column counts first, then sums the products — same complexity, counts each number's bits once.

ones × zeros, and no divide-by-two

No /2 is needed: the two endpoints come from disjoint groups, so each unordered pair is generated once (A from ones, C from zeros gives A–C, never also C–A). That's different from C(ones,2), which would count same-bit pairs — the opposite of what Hamming distance wants.

Five ways it slips

Sum over all pairs? Count contribution, don't build pairs

When a problem asks for a sum of some property over every pair and that property decomposes into independent components (here, bits), swap the order of counting: for each component, count how many pairs it contributes to. Quadratic pair enumeration collapses to O(B·n) with B a small constant.

Three questions unlock the whole family: can the score split into independent components? For one component, what makes a pair contribute? Can I count those pairs without listing them? Here: bits, differing bits, and ones × zeros.

Reconstruct it, don't memorize it

1. Hamming distance = differing bits = set bits of a XOR b; I need the sum over all pairs.
2. Pairwise enumeration is O(n²) — instead, fix a bit and count across all numbers.
3. At each bit the numbers split into ones and zeros; a pair differs iff it straddles the split.
4. So that bit contributes ones × zeros (disjoint groups → no divide-by-two).
5. Sum over all 31 bits in long. O(n) time, O(1) space.