Question

link

Hamming distance between two strings of equal length is the number of positions at which the corresponding symbols are different.

Write a function that takes a list of binary numbers and returns the sum of the hamming distances for each pair.

Do it in O(n) time.

Solution

The naive solution is O(n^2), so we simplify this question by using {0,0,0,1,1} as input. The output in this case would be 6. Why? Because 3 x 2 = 6.

So the equation for solution would be:

distance (for a bit) = number of ‘1’s * number of ‘0’s

The final answer would be the sum of distances for all bits. The solution is from this blog.

Code

Great solution, not written by me 

int hammingDist(int[] nums) {

	int[] bits = new int[32];

	for (int i = 0; i < nums.length; i++) {
		int one = 1;
		int j = 0;

		while (nums[i] != 0) {
			if ((nums[i] & one) != 0)
				bits[j]++;
			j++;
			nums[i] = nums[i] >> 1;
		}
	}

	int ans = 0;
	for (int i = 0; i < 32; i++) {
		ans += bits[i] * (nums.length - bits[i]);
	}

	return ans;
}