leetcode(3)

Description

The Hamming distance between two integers is the number of positions at which the corresponding bits are different.</br>
Now your job is to find the total Hamming distance between all pairs of the given numbers.</br>
Example:</br>
Input: 4, 14, 2</br>
Output: 6</br>

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:</br>
HammingDistance(4, 14) + HammingDistance(4, 2) + HammingDistance(14, 2) = 2

思路
如果用组合的方法也能做，但是复杂度太高了，现在拆解一下这个问题</br>
4   0100 </br>
2   0010 </br>
14 1110 </br>
第一位大家都是0，没有不同；第二位，一个0，两个1，那么比较的话，会出现2次不同；第三位，两个1，一个0，2次不同；第四位，两个0，一个1，两次不同。最后有6次不同。</br>
以此类推到32bits</br>
Submission

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

class Solution(object):
    def totalHammingDistance(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        res=0
        for i in range(32):
            count_one=0
            for num in nums:
                count_one+=(num>>i)&1
            count_zero=len(nums)-count_one
            count_mul=count_one*count_zero
            res+=count_mul
        return res