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²), 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;
}