LeetCode Total Hamming Distance

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.

The original problem is here.

My Solution

I solve this problem in C++, as below:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
class Solution {
public:
    int totalHammingDistance(vector<int>& nums) {
        int res = 0;
        while (isContainNonZero(nums)) {
            int count1bit=0, count0bit=0;
            for (int i = 0; i < nums.size(); i++) {
                if(nums[i] & 1)
                    count1bit++;
                else
                    count0bit++;
                
                nums[i] >>= 1;
            }
            res += count1bit * count0bit;
        }
        return res;
    }
    
    int isContainNonZero(vector<int>& nums) {
        for (int i = 0; i < nums.size(); i++){
            if (nums[i] > 0) {
                return true;
            }
        }
        return false;
    }
};

Note

如果直接两两计算汉明距离，最后求和，结果会超时。
解决方法是从低位到高位依次统计所有数的1和0的个数，每位的汉明距离就是1和0个数的乘积。
最后把每位的汉明距离相加即可得到最终结果。