LeetCode 477 - Total Hamming Distance

https://leetcode.com/problems/total-hamming-distance/

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.

X. Bit Counting
https://leetcode.com/problems/total-hamming-distance/discuss/96226/java-on-time-o1-space

For each bit position 1-32 in a 32-bit integer, we count the number of integers in the array which have that bit set. Then, if there are n integers in the array and k of them have a particular bit set and (n-k) do not, then that bit contributes k*(n-k) hamming distance to the total.

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;
}

https://zyfu0408.gitbooks.io/interview-preparation/content/bit-manipulation/bit.html
这题brute force的做法是两重for循环，用上一题的方法，两两比较，O(n ^ 2)的时间复杂度，超时了。

O(n)的复杂度的做法是，外层的for循环遍历int上的每一位，内层的for循环遍历数组，统计每一位出现了1的count，那该位的hamming distance就是count * (array.length - count)。

    public int totalHammingDistance(int[] nums) {
        int total = 0;
        for (int i = 0; i < 32; i++) {
            int count = 0;
            for (int num: nums) {
                if ((num >> i & 1) == 1) {
                    count++;
                }
            }
            total += count * (nums.length - count);
        }
        return total;
    }

    public int hammingDistance(int x, int y) {
        int count = 0;
        for (int i = 0; i < 32; i++) {
            int n1 = x >> i & 1;
            int n2 = y >> i & 1;
            if (n1 != n2) {
                count++;
            }
        }
        return count;
    }

http://startleetcode.blogspot.com/2016/12/477-total-hamming-distance.html
May use the bitwise operation to reduce the time complexity. All the numbers can be viewed as 32 bits with 0s and 1s. So for each bit, we just need to count the total number of 1s, then the total number of 0s will be (total numbers - the numbers of 1s). And the contribution to the Hamming distance will be count of 1s times the count of 0s. Similarly argument can be applied to all the rest bits.

1.     int totalHammingDistance(vector<int>& nums) {
2.         int res = 0;
3.         for(int i=0; i<32; ++i){
4.             int one = 0;
5.             for(int j=0; j<nums.size(); ++j){
6.                 if((1<<i) & nums[j]) ++one;//one is the numbers of 1s;
7.             }
8.             res += one*(nums.size()-one);// nums of 1s x nums of 0s
9.         }
10.         return res;
11.     }

http://bookshadow.com/weblog/2016/12/18/leetcode-total-hamming-distance/

按位统计各整数的二进制0与1的个数之和，分别记为zero[i], 和one[i]

ans = ∑(zero[i] * one[i]),  i∈[0, 31]

def totalHammingDistance(self, nums): """ :type nums: List[int] :rtype: int """ ans = 0 for x in range(32): mask = 1 << x zero = one = 0 for num in nums: if num & mask: one += 1 else: zero += 1 ans += zero * one return ans
X.
https://www.jianshu.com/p/8f127578fe73

那么应该怎么做这道题目呢？题目中的 Explanation 其实是一种误导，我们真的有必要两两组合分别求 Hamming Distance 吗？其实是没有必要的，一次循环能否取得所有的 Hamming Distance？
通过分析得出，Hamming Distance 其实就是每一位的异同。那么这道题目就可以转化为：求x个数每两个数的组合中，每一位的异同数量。想到这里，就会发现其实x个数中每个数的数值并不重要，重要的是每一位有多少个0和多少个1。

https://zhuhan0.blogspot.com/2017/08/leetcode-477-total-hamming-distance.html

A more efficient way to solve this is to iterate through the bits. Since max(nums) < 10^9, I know that the numbers won't take more than 32 bits. Say for one of these bits, there are k numbers with that bit on, so there are n - k numbers with that bit off. Then that particular bit will add k(n - k) to the total hamming distance.

    public int totalHammingDistance(int[] nums) {
        int[] bitCounts = new int[32];
        for (int num : nums) {
            int i = 0;
            while (num > 0) {
                bitCounts[i] += num & 1;
                num >>= 1;
                i++;
            }
        }
        
        int length = nums.length;
        int total = 0;
        for (int count : bitCounts) {
            total += count * (length - count);
        }
        return total;
    }

X. Brute Force
https://github.com/veronikabenkeser/LeetCode/blob/master/477.%20Total%20Hamming%20Distance
http://blog.csdn.net/zhouziyu2011/article/details/53726081

(1)遍历数组nums，对每一个nums[i]，求其余后面的每一个nums[j]的Hamming Distance。

(2)求x与y的Hamming Distance的方法：

---1)先求x^y的结果res。

---2)再依次求32位res的每一位与1进行与操作的结果，若不为0，则Hamming Distance加一。

1.     public int totalHammingDistance(int[] nums) {  
2.         int len = nums.length;  
3.         if (len == 0)  
4.             return 0;  
5.         int result = 0;  
6.         for (int i = 0; i < len - 1; i++) {  
7.             for (int j = i + 1; j < len; j++)  
8.                 result += hammingDistance(nums[i], nums[j]);  
9.         }  
10.         return result;  
11.     }  
12.     public int hammingDistance(int x, int y) {  
13.         int res = x ^ y;  
14.         int count = 0;  
15.         for (int i = 0; i < 32; i++) {  
16.             if ((res & 1) != 0)  
17.                 count++;  
18.             res >>= 1;  
19.         }  
20.         return count;  
21.     }  

https://discuss.leetcode.com/topic/72099/share-my-o-n-c-bitwise-solution-with-thinking-process-and-explanation