Total Hamming Distance Problem

Problem

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.

Examples

Example 1:

1
2
3
4
5
6
7
8

Input:
nums = [4,14,2]
Output:
 6
Explanation: In binary representation, the 4 is 0100, 14 is 1110, and 2 is 0010 (just
showing the four bits relevant in this case).
The answer will be:
HammingDistance(4, 14) + HammingDistance(4, 2) + HammingDistance(14, 2) = 2 + 2 + 2 = 6.

Example 2:

1
2
3
4

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

Solution

Method 1 – Bitwise Counting

Intuition

Instead of comparing every pair, we count for each bit position how many numbers have a 1 and how many have a 0. Each pair with different bits at that position contributes 1 to the total Hamming distance.

Approach

  1. For each bit position (0 to 31 for 32-bit integers):
    • Count how many numbers have a 1 at that position (cnt1).
    • The rest have a 0 (cnt0 = n - cnt1).
  2. For each bit, the number of differing pairs is cnt1 * cnt0.
  3. Sum this for all bit positions to get the answer.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

class Solution {
public:
    int totalHammingDistance(vector<int>& nums) {
        int ans = 0, n = nums.size();
        for (int i = 0; i < 32; ++i) {
            int cnt1 = 0;
            for (int x : nums) cnt1 += (x >> i) & 1;
            ans += cnt1 * (n - cnt1);
        }
        return ans;
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

func totalHammingDistance(nums []int) int {
    ans, n := 0, len(nums)
    for i := 0; i < 32; i++ {
        cnt1 := 0
        for _, x := range nums {
            if (x>>i)&1 == 1 {
                cnt1++
            }
        }
        ans += cnt1 * (n - cnt1)
    }
    return ans
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

class Solution {
    public int totalHammingDistance(int[] nums) {
        int ans = 0, n = nums.length;
        for (int i = 0; i < 32; i++) {
            int cnt1 = 0;
            for (int x : nums) cnt1 += (x >> i) & 1;
            ans += cnt1 * (n - cnt1);
        }
        return ans;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

class Solution {
    fun totalHammingDistance(nums: IntArray): Int {
        var ans = 0
        val n = nums.size
        for (i in 0 until 32) {
            var cnt1 = 0
            for (x in nums) cnt1 += (x shr i) and 1
            ans += cnt1 * (n - cnt1)
        }
        return ans
    }
}
1
2
3
4
5
6
7
8

class Solution:
    def totalHammingDistance(self, nums: list[int]) -> int:
        ans = 0
        n = len(nums)
        for i in range(32):
            cnt1 = sum((x >> i) & 1 for x in nums)
            ans += cnt1 * (n - cnt1)
        return ans
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

impl Solution {
    pub fn total_hamming_distance(nums: Vec<i32>) -> i32 {
        let mut ans = 0;
        let n = nums.len() as i32;
        for i in 0..32 {
            let cnt1 = nums.iter().filter(|&&x| (x >> i) & 1 == 1).count() as i32;
            ans += cnt1 * (n - cnt1);
        }
        ans
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

class Solution {
    totalHammingDistance(nums: number[]): number {
        let ans = 0, n = nums.length;
        for (let i = 0; i < 32; i++) {
            let cnt1 = 0;
            for (const x of nums) cnt1 += (x >> i) & 1;
            ans += cnt1 * (n - cnt1);
        }
        return ans;
    }
}

Complexity

  • ⏰ Time complexity: O(32n) — We scan all 32 bits for each number, so it’s linear in the number of elements.
  • 🧺 Space complexity: O(1) — Only a few counters are used, no extra space proportional to input size.