Total Hamming Distance

Master this topic with zero to advance depth.

Total Hamming Distance

The Hamming distance between two integers is the number of positions at which the corresponding bits are different. Return the sum of Hamming distances between all pairs of integers in nums.

Medium

Examples

Input: nums = [4,14,2]
Output: 6
HammingDistance(4, 14) + HammingDistance(4, 2) + HammingDistance(14, 2) = 2 + 2 + 2 = 6.

Approach 1

Level I: Brute Force (Check All Pairs)

Intuition

The most direct way is to iterate through every pair in the array, calculate their Hamming distance, and sum them up.

Thought Process

Initialize totalDist = 0.
For each pair $(i, j)$ $(i, j)$ where $i < j$ $i < j$ :
- Calculate Hamming distance: Integer.bitCount(nums[i] ^ nums[j]).
- Add to totalDist.
Return totalDist.

Pattern: Nested Iteration

⏱ O(N^2) - To check all $N(N-1)/2$ pairs.💾 O(1) - Constant space.

java

public class Solution {
    public int totalHammingDistance(int[] nums) {
        int total = 0;
        for (int i = 0; i < nums.length; i++) {
            for (int j = i + 1; j < nums.length; j++) {
                total += Integer.bitCount(nums[i] ^ nums[j]);
            }
        }
        return total;
    }
}

Approach 2

Level II: Iterative Bit Verification

Intuition

We can calculate the Hamming distance for each pair by iterating through the numbers and checking each bit. This is similar to the brute force but slightly more structured.

⏱ $O(N^2 \cdot 32)$💾 $O(1)$

java

class Solution {
    public int totalHammingDistance(int[] nums) {
        int total = 0, n = nums.length;
        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                int xor = nums[i] ^ nums[j];
                for (int k = 0; k < 32; k++) {
                    if (((xor >> k) & 1) == 1) total++;
                }
            }
        }
        return total;
    }
}

Approach 3

Level III: Optimal (Bit Counting per Position)

Intuition

Instead of checking pairs, we can check bit positions. For any bit position $i$ , if $k$ numbers have the $i$ -th bit set to 1, and $n-k$ numbers have it set to 0, then there are $k \cdot (n-k)$ pairs that differ at this position.

Thought Process

Initialize total = 0.
For each bit position $0$ $0$ to $31$ $31$ :
- Count numbers $k$ with $i$ -th bit set.
- total += k * (n - k).
Return total.

Pattern: Positional Counting

⏱ O(N) - Single pass over the array for each of the 32 bits.💾 O(1) - Constant space.

Detailed Dry Run

nums: [4, 14, 2], n=3 Bit Pos 1: Bits are {0, 1, 0}. k=1, n-k=2. Pairs = 12 = 2. Bit Pos 2: Bits are {1, 1, 0}. k=2, n-k=1. Pairs = 21 = 2. Bit Pos 3: Bits are {0, 1, 0}. k=1, n-k=2. Pairs = 1*2 = 2. Total: 2+2+2 = 6.

java

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

← Previous QuestionDivide Two Integers

Next Question →Minimum Flips to Make a OR b Equal to c

Found an issue or have a suggestion?

Help us improve! Report bugs or suggest new features on our Telegram group.