477. Total Hamming Distance

Problem

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:

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

Problem Summary

The Hamming distance between two integers refers to the number of positions at which the corresponding bits of their binary representations are different. Calculate the total Hamming distance between any two numbers in an array.

Solution Ideas

• Calculate the total Hamming distance of all pairs of elements in an array. The definition of Hamming distance is the total number of differing binary bits between two numbers. Then we can scan the 32 binary bits of each element in the array one by one. When scanning a certain bit, suppose k elements have a value of 1 at this bit, and n - k elements have a value of 0 at this bit. Then the Hamming distance of all pairs of elements at this bit is k*(n-k). After scanning all 32 bits, the accumulated Hamming distance is the Hamming distance of all pairs of elements.

Code

package leetcode

func totalHammingDistance(nums []int) int {
	total, n := 0, len(nums)
	for i := 0; i < 32; i++ {
		bitCount := 0
		for j := 0; j < n; j++ {
			bitCount += (nums[j] >> uint(i)) & 1
		}
		total += bitCount * (n - bitCount)
	}
	return total
}

// Brute-force solution times out!
func totalHammingDistance1(nums []int) int {
	res := 0
	for i := 0; i < len(nums); i++ {
		for j := i + 1; j < len(nums); j++ {
			res += hammingDistance(nums[i], nums[j])
		}
	}
	return res
}