LeetCode 477: Total Hamming Distance

Problem Restatement

We are given an integer array nums.

The Hamming distance between two integers is the number of bit positions where their binary representations are different.

We need to return the sum of Hamming distances over all pairs of integers in nums.

For example:

nums = [4, 14, 2]

Their binary forms are:

4  = 0100
14 = 1110
2  = 0010

Pair distances:

HammingDistance(4, 14) = 2
HammingDistance(4, 2)  = 2
HammingDistance(14, 2) = 2

So the answer is:

2 + 2 + 2 = 6

Input and Output

Function shape:

def totalHammingDistance(nums: list[int]) -> int:
    ...

Examples

Example 1:

nums = [4, 14, 2]

Binary view:

4  = 0100
14 = 1110
2  = 0010

Compare each pair:

4  vs 14: 0100 vs 1110 differs in 2 places
4  vs 2 : 0100 vs 0010 differs in 2 places
14 vs 2 : 1110 vs 0010 differs in 2 places

Answer:

6

Example 2:

nums = [4, 4, 4]

Every pair has equal numbers.

So every Hamming distance is 0.

Answer:

0

Example 3:

nums = [0, 1]

Binary view:

0 = 0
1 = 1

They differ in one bit.

Answer:

1

First Thought: Brute Force

The direct method is to compare every pair.

For each pair (nums[i], nums[j]), compute:

nums[i] ^ nums[j]

XOR marks the differing bit positions with 1.

Then count the number of 1 bits.

class Solution:
    def totalHammingDistance(self, nums: list[int]) -> int:
        ans = 0
        n = len(nums)

        for i in range(n):
            for j in range(i + 1, n):
                ans += (nums[i] ^ nums[j]).bit_count()

        return ans

This is easy to write and correct for small inputs.

Problem With Brute Force

If there are n numbers, there are about:

n * (n - 1) / 2

pairs.

So the brute force method takes O(n^2) pair checks.

That becomes too slow when nums is large.

We need to avoid comparing each pair one by one.

Key Insight

Hamming distance can be counted bit by bit.

At one bit position, a pair contributes 1 to the answer only when one number has bit 0 and the other number has bit 1.

So for each bit position:

1. Count how many numbers have a 1 at that bit.
2. Count how many numbers have a 0 at that bit.
3. Multiply them.

If:

ones = count of numbers with bit 1
zeros = count of numbers with bit 0

then this bit contributes:

ones * zeros

Why?

Every number with 1 can pair with every number with 0.

Each such pair differs at this bit.

For nums = [4, 14, 2]:

4  = 0100
14 = 1110
2  = 0010

Look at each bit column:

Total:

0 + 2 + 2 + 2 = 6

Algorithm

Set ans = 0.

For each bit position from 0 to 30:

1. Count how many numbers have that bit set.
2. Let ones be that count.
3. Let zeros = len(nums) - ones.
4. Add ones * zeros to ans.

Return ans.

We use 30 or 31 bit positions depending on constraints. In Python, using 31 positions is safe for common LeetCode integer constraints here.

Correctness

Consider any fixed bit position.

A pair contributes 1 to the Hamming distance at this position exactly when the two numbers have different bits at this position.

There are only two possible bit values: 0 and 1.

If ones numbers have bit 1, and zeros numbers have bit 0, then every mixed pair contributes once. The number of mixed pairs is:

ones * zeros

Pairs where both bits are 0 contribute nothing at this position.

Pairs where both bits are 1 also contribute nothing at this position.

Therefore, ones * zeros is exactly the total contribution of this bit position across all pairs.

The algorithm repeats this for every relevant bit position. Hamming distance is the sum of differences over all bit positions, so summing the contribution of every bit gives the total Hamming distance over all pairs.

Thus the algorithm returns the required answer.

Complexity

The number of checked bit positions is fixed, so the algorithm is linear in the length of nums.

Implementation

class Solution:
    def totalHammingDistance(self, nums: list[int]) -> int:
        ans = 0
        n = len(nums)

        for bit in range(31):
            ones = 0

            for num in nums:
                if num & (1 << bit):
                    ones += 1

            zeros = n - ones
            ans += ones * zeros

        return ans

Code Explanation

We keep the total answer here:

ans = 0

Then we check each bit position:

for bit in range(31):

For each bit position, count how many numbers have that bit set:

if num & (1 << bit):
    ones += 1

The expression:

1 << bit

creates a mask with only that bit turned on.

For example:

After counting ones, we compute:

zeros = n - ones

Then this bit contributes:

ones * zeros

Finally, return the total:

return ans

More Compact Implementation

Python can count ones with a generator expression:

class Solution:
    def totalHammingDistance(self, nums: list[int]) -> int:
        ans = 0
        n = len(nums)

        for bit in range(31):
            ones = sum((num >> bit) & 1 for num in nums)
            ans += ones * (n - ones)

        return ans

This version uses the same idea.

Testing

def run_tests():
    s = Solution()

    assert s.totalHammingDistance([4, 14, 2]) == 6
    assert s.totalHammingDistance([4, 4, 4]) == 0
    assert s.totalHammingDistance([0, 1]) == 1
    assert s.totalHammingDistance([0, 0, 1, 1]) == 4
    assert s.totalHammingDistance([1, 2, 3]) == 4

    print("all tests passed")

run_tests()

Test meaning: