TotalHammingDistance [source code]

public class TotalHammingDistance {
static
/******************************************************************************/
public class Solution {
    public int totalHammingDistance(int[] nums) {
        int n = nums.length;
        boolean[][] digits = new boolean[n][32];
        for (int i = 0; i < n; i++) {
            char[] numDigits = Integer.toBinaryString(nums[i]).toCharArray();
            for (int j = 0; j < 31 && j < numDigits.length; j++)
                digits[i][31 - j] = numDigits[numDigits.length - 1 - j] == '1' ? true : false;
        }
        int res = 0;
        for (int i = 0; i < 32; i++) {
            int countOne = 0;
            for (int j = 0; j < n; j++)
                if (digits[j][i])
                    countOne++;
            if (countOne > 0 && countOne < n)
                res += countOne * (n - countOne);
        }
        return res;
    }
}
/******************************************************************************/

    public static void main(String[] args) {
        TotalHammingDistance.Solution tester = new TotalHammingDistance.Solution();
        int[] inputs = {
            4, 14, 2, 6,
        };
        for (int i = 0; i < inputs.length / 4; i++) {
            int[] nums = {inputs[4 * i], inputs[1 + 4 * i], inputs[2 + 4 * i]};
            int ans = inputs[3 + 4 * i];
            System.out.println(Printer.separator());
            int res = tester.totalHammingDistance(nums);
            System.out.println(
                Printer.wrapColor(Printer.array(nums), "magenta") +
                " -> " + res +
                Printer.wrapColor(", expected: " + ans, ans == res ? "green" : "red")
                );
        }
    }
}

笨办法肯定是每一个pair都拿出来算一下, 最后求和; 不过这个题目既然让你算一大组里面所有的数字之间的hamming distance, 那么按理是应该有什么加速的思路; 也就是你算N个数字的这个total, 应该是能够做到比C N 2个结果求和还要快的;

自己动笔画了一下笨办法的人逻辑, 希望找到一个优化的思路, 然后好像有点灵感了(很多时候灵感给你的感觉就是"不太靠谱", 不过不要太早放弃, 给了一分钟的力还是做不出来再放弃);

这个sum类的题目, 很多时候的一个思路就是contribution做法; 比如我们这里要找的是different bits, 事实上, 每一个bit跟每一个与之不同的bit, essentially都是会产生一个贡献;

另外这里还用到的一个思路, 就是直接对每一个bit位置进行统计, 这个在很多bit问题当中都出现过; 尤其是这里是一个array of numbers, 长度未定, 那么诱发这种做法的动机其实就更加强烈;

理解了这个insight之后这个问题就不困难了, 不过最后的速度倒是很难看: 60ms (6%);

后来想了一下大概还可以优化的是, 第二个pass不用固定一定要走满32位, 事实上, 在第一个pass的时候我们可以记录所有的数最长的长度, 这个也就是the leftmost possible position that a difference can occur. 不过这个其实也是一个constant factor的改善而已吧, 有可能造成这么大的速度差别吗? 如果说从本质上重新改写这个算法, 好像又没有更好的做法;

editorial大概看了一下, 写的比较蠢, 最好的一个解法其实就跟我的做法是一样的(比较差的一个做法也是分别对32个bit进行操作, 不过每一个bit里面还是用xor来做, 好像是c++有一个什么built-in的东西可以很快的做这个东西);

discussion最优解:

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

比我的精简一些, 一个pass就搞定了; 另外他这个是O(1)的空间; 事实上这个问题确实不需要额外的空间; 不过不做Premature Optmization也不值得责怪好吧. 这种程度的优化, 真正假如Follow-Up需要优化, 也不是想不出来的;

for each "column" or bit position, once you count the number of set bits you can figure out the number of pairs that will contribute to the count using combination logic.

Consider you have 10 numbers and only one of them is a 1 the rest are zeros. How many (1, 0) pairs can you make? Clearly you can make 9, pair the 1 with each of the other 9 zeros. If you have 2 ones, you can pair each of those with the other 8 zeros giving 2*8 = 16. Keep going and you see that you can pair each 1 with each zero so the number of pairs is just the number of 1's times the number of 0's.

This would be an O(32 * n) solution which is an O(n) solution, no space used.

回复里面一个大概的解释, 不过这个算法本身总体也不是完全无法理解;

根据discussion里面的反应来看, 这题好像还难住了不少人; 所以我感觉我只要胆子大一点, 很多难题还是做的出来的;

另外记住一点, 这个算法当时我自己想到这个优化的一个原因也是因为肯用人逻辑去理解例子. 这个才是你面对一个新题的时候最重要的法宝;

discussion基本没有其他更好的解法了, 这个题目好像也是个一招鲜的题目;

Problem Description

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.

Difficulty:Medium
Total Accepted:18.3K
Total Submissions:39.3K
Contributor: [email protected]
Companies
facebook
Related Topics
bit manipulation
Similar Questions
Hamming Distance