LeetCode #477 Total Hamming Distance

Posted on | Post modified | In , , , , , , ,

Problem

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

1
2
3
4
5
6
7
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.

Solution1

Method: Backtracking

Time Complexity:

Space Complexity:

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
class Solution:
    def __init__(self):
        self.pairs = []
        self.result = 0

    def backtracking(self, answer, kth, info):
        if sum(answer) == 2 or kth == len(info):
            if sum(answer) == 2:
                p = [info[idx - 1] for idx, flag in enumerate(answer) if flag]
                self.result += bin(p[0] ^ p[1]).count('1')
        else:
            kth += 1
            candidates = [True, False]
            for candidate in candidates:
                answer.append(candidate)
                self.backtracking(answer, kth, info)
                answer.pop()

        
    def totalHammingDistance(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        self.backtracking([], 0, nums)
        
        return self.result

Solution2

Method: Bit Manipulation

Time Complexity: O(n logv)

Space Complexity:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution:    
    def totalHammingDistance(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        ans = 0
        mask = 1

        for j in range(0, 32):
            ones = zeros = 0

            for num in nums:
                if num & mask:
                    ones += 1
                else:
                    zeros += 1
            
            ans += ones * zeros
            mask = mask << 1

        return ans