Problem statement

Given an integer array nums, return the sum of the Hamming distances between all pairs of its elements.

Example 1

Input: nums = [4,14,2]
Output: 6
Explanation: The three pairwise distances are 2, 2 and 2.

Example 2

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

Example 3

Input: nums = [0]
Output: 0

Constraints

• 1 <= nums.length <= 40
• 0 <= nums[i] <= 1000000000
• The answer fits in a signed 32-bit integer.

Hints for Total Hamming Distance

1. Hint 1

   Comparing every pair is O(n²) — count by bit position instead.

2. Hint 2

   For one bit position, let k be how many numbers have it set.

3. Hint 3

   Every set/unset pairing contributes 1, so that position adds k * (n - k) to the total.

How to solve Total Hamming Distance

Handle each bit position separately: if k numbers have the bit set, that position contributes k · (n - k) to the total over all pairs.

Approach

1. For each bit, count the numbers with it set.
2. Add ones · (n - ones).

Why it works

Each pair's Hamming distance is a sum over positions, so the total is a sum over positions of the number of pairs that differ there — one from the set group and one from the unset group.

Complexity

• Time — O(31 · n)
• Space — O(1)

Pitfalls

• The pairwise O(n²) loop is correct but too slow for large n.

Reference solution

Python

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

Java

public static int totalHammingDistance(int[] nums) {
    int total = 0;
    int n = nums.length;
    for (int bit = 0; bit < 31; bit++) {
        int ones = 0;
        for (int x : nums) ones += (x >> bit) & 1;
        total += ones * (n - ones);
    }
    return total;
}

C++

int totalHammingDistance(vector<int>& nums) {
    int total = 0;
    int n = (int) nums.size();
    for (int bit = 0; bit < 31; bit++) {
        int ones = 0;
        for (int x : nums) ones += (x >> bit) & 1;
        total += ones * (n - ones);
    }
    return total;
}

JavaScript

var totalHammingDistance = function(nums) {
    let total = 0;
    for (let bit = 0; bit < 31; bit++) {
        let ones = 0;
        for (let i = 0; i < nums.length; i++) ones += (nums[i] >> bit) & 1;
        total += ones * (nums.length - ones);
    }
    return total;
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

More arrays problems

• Implement Router Medium
• Design Memory Allocator Medium
• Design a Food Rating System Medium
• Design an ATM Machine Medium
• Design Bitset Medium
• Range Frequency Queries Medium