Total Hamming Distance

medium array math bit manipulation

Problem

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

Inputnums = [4, 14, 2]

Output6

HD(4,14)+HD(4,2)+HD(14,2) = 2 + 2 + 2 = 6. Or: at each bit, count ones k, zeros n−k; contribute k·(n−k).

nums

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

function totalHammingDistance(nums) {
  const n = nums.length;
  let total = 0;
  for (let b = 0; b < 32; b++) {
    let ones = 0;
    for (const x of nums) ones += (x >> b) & 1;
    total += ones * (n - ones);
  }
  return total;
}

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

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

Explanation

The Hamming distance between two numbers is how many bit positions they differ in, and we want the sum over all pairs. Comparing every pair directly would be O(n^2), but we can be smarter by looking at one bit position at a time.

The key idea: pairs only differ at a given bit if one number has a 1 there and the other has a 0. So if at bit b there are k ones and n - k zeros, then exactly k * (n - k) pairs differ at that bit.

Every differing bit contributes 1 to some pair's distance, so we can just add up k * (n - k) across all 32 bit positions to get the total directly.

The code loops b from 0 to 31, counts the ones at that bit with (x >> b) & 1 summed over all numbers, and adds ones * (n - ones) to total.

Example: nums = [4, 14, 2]. Adding up the per-bit contributions yields 6, the same as HD(4,14) + HD(4,2) + HD(14,2) = 2 + 2 + 2.

Time: O(n · 32) Space: O(1)