Solutions

1. Brute Force

O(n²) time | O(1) space

Intuition

We can check every possible pair of numbers in the array and add up their Hamming distances.

The XOR of two numbers has a 1 in exactly the places where they differ, so the number of 1 bits in it is their Hamming distance.

Algorithm

Iterate through the outer loop from the first element to the last element with i index.
For each outer loop iteration, iterate through the inner loop from the element at i + 1 to the last element with j index.
Add the number of 1 bits in the XOR of the elements at i and j to the total.
Return the total when both loops finish.

4 ^ 14 = 10, 2 bits differ, total = 2

1 / 4

Code

def totalHammingDistance(nums: list[int]) -> int:
    total = 0
    for i in range(len(nums)):
        for j in range(i + 1, len(nums)):
            total += (nums[i] ^ nums[j]).bit_count()
    return total

/**
 * @param {number[]} nums
 * @returns {number}
 */
var totalHammingDistance = function (nums) {
  let total = 0
  for (let i = 0; i < nums.length; i++) {
    for (let j = i + 1; j < nums.length; j++) {
      total += countOnes(nums[i] ^ nums[j])
    }
  }
  return total
}

function countOnes(n) {
  let count = 0
  while (n !== 0) {
    n &= n - 1
    count++
  }
  return count
}

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;
    }
}

2. Counting Bits

O(n) time | O(1) space

Intuition

Every number is at most $10^9$ , which is less than $2^{30}$ , so each number has at most 30 bits.

If we count the ones and zeros among all numbers at each bit position, their product is the number of pairs that differ at that position. Adding these products over all 30 positions gives the total.

num >> bit & 1 gets the bit of each number at position bit by shifting it right and taking AND with 1.

Algorithm

Iterate through the outer loop from the bit position 0 to 29 with bit index.
For each outer loop iteration, iterate through the inner loop from the first element to the last element and count ones, the number of elements that have 1 at position bit.
When the inner loop finishes, add ones * (n - ones) to the total, where n is the number of elements.
Return the total when both loops finish.

3210

0 ones, 3 zeros, 0 * 3 = 0, total = 0

1 / 5

Code

def totalHammingDistance(nums: list[int]) -> int:
    total = 0
    for bit in range(30):
        ones = sum(num >> bit & 1 for num in nums)
        total += ones * (len(nums) - ones)
    return total

/**
 * @param {number[]} nums
 * @returns {number}
 */
var totalHammingDistance = function (nums) {
  let total = 0
  for (let bit = 0; bit < 30; bit++) {
    let ones = 0
    for (const num of nums) {
      ones += (num >> bit) & 1
    }
    total += ones * (nums.length - ones)
  }
  return total
}

class Solution {
    public int totalHammingDistance(int[] nums) {
        int total = 0;
        for (int bit = 0; bit < 30; bit++) {
            int ones = 0;
            for (int num : nums) {
                ones += num >> bit & 1;
            }
            total += ones * (nums.length - ones);
        }
        return total;
    }
}