Total Hamming Distance

Question

The Hamming distance between two integers is the number of positions at which the corresponding bits are different.

Now your job is to find the total Hamming distance between all pairs of the given numbers.

Example:

Input: 4, 14, 2

Output: 6

Explanation: In binary representation, the 4 is 0100, 14 is 1110, and 2 is 0010 (just
showing the four bits relevant in this case). So the answer will be:
HammingDistance(4, 14) + HammingDistance(4, 2) + HammingDistance(14, 2) = 2 + 2 + 2 = 6.

Note:

• Elements of the given array are in the range of 0 to 10^9
• Length of the array will not exceed 10^4.

Tags

• Bit Manipulation

Thought

A naive approach is to utilize the solution in Hamming Distance, but it will cause the time limit exceeded because of the large test case.

It is necessary to consider this problem in another way and calculate the distance of the list of numbers together. Suppose we build a table. The width of the table is equal to the length of the binary string and the height of the table is equal to the length of the input list. Then each number can be represented by a row in this table.

Now we need to observe a specific column of the table, which represents a specific digit for all the binary string for the input numbers. It can be found that the Hamming Distance for this specific digit is equal to the multiplication between the number of '1' and the number of '0'. Thus, we can get a equation for counting the Hamming Distance for ith digit:

distance[i]=table[:][i].count('0') * table[:][i].count('1')

The total Hamming Distance will be: sum(distance).

Code

class Solution(object):
    def totalHammingDistance(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        bits = [[0, 0] for _ in xrange(32)]
        for num in nums:
            stringNum = format(num, 'b').zfill(32)
            for i in xrange(32):
                if stringNum[i] == '0':
                    bits[i][0] += 1
                else:
                    bits[i][1] += 1
        return sum(x*y for x, y in bits)