Code Implementation

class Solution:
    def totalHammingDistance(self, nums):
        total = 0
        n = len(nums)
        for i in range(32):
            bit_count = 0
            for num in nums:
                bit_count += (num >> i) & 1
            total += bit_count * (n - bit_count)
        return total
      

class Solution {
public:
    int totalHammingDistance(vector<int>& nums) {
        int total = 0, n = nums.size();
        for (int i = 0; i < 32; ++i) {
            int bitCount = 0;
            for (int num : nums) {
                bitCount += (num >> i) & 1;
            }
            total += bitCount * (n - bitCount);
        }
        return total;
    }
};
      

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

var totalHammingDistance = function(nums) {
    let total = 0, n = nums.length;
    for (let i = 0; i < 32; ++i) {
        let bitCount = 0;
        for (let num of nums) {
            bitCount += (num >> i) & 1;
        }
        total += bitCount * (n - bitCount);
    }
    return total;
};
      

Problem Description

You are given an array of integers nums. The Hamming distance between two integers is the number of positions at which the corresponding bits are different in their binary representations.

Your task is to compute the total Hamming distance between all pairs of integers in the array. That is, for every pair of indices (i, j) with i < j, calculate the Hamming distance between nums[i] and nums[j], and return the sum of all these distances.

• Each pair of elements is considered only once (no repeats or self-pairs).
• The input array can have up to 10⁴ elements, and each element is a non-negative integer (up to 2³¹ - 1).

Thought Process

At first glance, you might think to simply compare every pair of numbers in nums and compute their Hamming distance by converting them to binary and counting the differing bits. However, with up to 10,000 elements, this would require checking nearly 50 million pairs, which is too slow.

Instead, let's look for patterns. The Hamming distance between two numbers is the count of positions where their bits differ. If we examine each bit position across all numbers, we can count how many numbers have a 1 in that position and how many have a 0. Each pair where one number has a 1 and the other has a 0 at the same position contributes 1 to the total Hamming distance.

By focusing on bit positions instead of pairs, we can reduce the problem from O(n²) comparisons to O(n) per bit position, which is much faster.

Solution Approach

• Step 1: For each bit position (from 0 to 31, since integers are up to 32 bits), count how many numbers in nums have a 1 at that position.
• Step 2: For each bit position, let ones be the count of numbers with a 1, and zeros be the rest (n - ones).
• Step 3: The total number of pairs that differ at this bit is ones * zeros. Add this to the running total.
• Step 4: Repeat for all 32 bit positions and sum up the results.
• This approach works because every pair where the bits differ at a position contributes exactly 1 to the total Hamming distance, and the sum over all positions gives the full answer.

This method is efficient because it only looks at each bit in each number once, leading to O(32n) time complexity, which is effectively O(n) for practical purposes.

Example Walkthrough

Let's consider the input nums = [4, 14, 2].

• Binary representations:
  • 4 = 100
  • 14 = 1110
  • 2 = 10
• Let's check bit by bit (from least significant to most):
• Bit 0 (rightmost):
  • 4: 0, 14: 0, 2: 0 → all zeros, so 0 pairs differ
• Bit 1:
  • 4: 0, 14: 1, 2: 1 → two ones, one zero → 2 pairs differ (each one pairs with the zero)
• Bit 2:
  • 4: 1, 14: 1, 2: 0 → two ones, one zero → 2 pairs differ
• Bit 3:
  • 4: 0, 14: 1, 2: 0 → one one, two zeros → 2 pairs differ
• Bits 4 and above: all zeros, so no pairs differ.

Summing up: 0 (bit 0) + 2 (bit 1) + 2 (bit 2) + 2 (bit 3) = 6. So the answer is 6.

Time and Space Complexity

• Brute-force approach:
  • Time: O(n² × k), where n is the array length and k is the number of bits (up to 32). This is because you check every pair and every bit.
  • Space: O(1) extra (not counting input).
• Optimized bitwise approach (this solution):
  • Time: O(32n) = O(n), since you process each of 32 bits for all n numbers.
  • Space: O(1) extra, just a few counters.

The optimized approach is much faster and suitable for large inputs.

Summary

To efficiently compute the total Hamming distance among all pairs in an array, we avoid comparing every pair directly. Instead, we count the number of ones and zeros at each bit position and use their product to sum the differing pairs. This clever bitwise counting reduces the time complexity from quadratic to linear, making it both fast and elegant.