Total Hamming Distance

Problem

Return the sum of Hamming distances between every pair of integers in nums.

Constraints

• 1 ≤ n ≤ 10⁴

Approach — Core Patterns

This is a Core Patterns problem. The idea: pick the data structure best matched to the constraints and solve it in one clean pass. Work through the reference code below line by line, then re-derive it yourself in the editor — that's how the pattern sticks.

Complexity: see the walkthrough below.

Solution code

Python

class Solution:
    def totalHammingDistance(self, nums):
        total = 0
        n = len(nums)
        for b in range(32):
            ones = sum((x >> b) & 1 for x in nums)
            total += ones * (n - ones)
        return total

Java

class Solution {
    public int totalHammingDistance(int[] nums) {
        int total = 0, n = nums.length;
        for (int b = 0; b < 32; b++) {
            int ones = 0;
            for (int x : nums) if (((x >> b) & 1) == 1) ones++;
            total += ones * (n - ones);
        }
        return total;
    }
}

Practice it

Reading a solution isn't the same as being able to write it under pressure. Open this problem in the in-browser editor, hide the solution, and solve it from scratch — your code runs against real test cases instantly.