477. Total Hamming Distance

Tags: [bit], [bit_manipulation], [xor]

Com: {fb}

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

TheHamming 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 of0to10^9
2. Length of the array will not exceed10^4

Better Understanding Solution:

class Solution(object):
    def totalHammingDistance(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        if not nums or len(nums) < 2:
            return 0

        size = len(nums)
        counter = 0
        for i in xrange(32):
            num_of_ones = 0
            for num in nums:
                num_of_ones += (num >> i) & 1

            counter += num_of_ones * (size - num_of_ones)

        return counter

Revelation:

• When meet the bit manipulation problem, and need calculate something total, we can think about iterate 32 bit position.

Note:

• Time complexity = O(n), n is the number of elements of the given nums.

Solution:

class Solution(object):
    def totalHammingDistance(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """

        # Assume there are 32 bits in one integer
        total_distance = 0
        for i in xrange(32):
            one_counter = 0
            for j in xrange(len(nums)):
                if nums[j] & 1 == 1:
                    one_counter += 1

                nums[j] >>= 1

            zero_counter = len(nums) - one_counter
            diff_counter = zero_counter * one_counter
            total_distance += diff_counter

        return total_distance

Time Limited Exceeded

class Solution(object):
    def totalHammingDistance(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """

        index_set = set()
        result = []
        self.totalHammingDistanceHelper(nums, 0, result, index_set)
        return sum(result)

    def totalHammingDistanceHelper(self, nums, index, result, index_set):
        # Base case.
        if index + 1 >= len(nums):
            return

        for i in xrange(index + 1, len(nums)):
            indexes = '{}-{}'.format(index, i)
            if indexes in index_set:
                continue

            index_set.add(indexes)
            result.append(self.getHammingDistance(nums[index], nums[i]))
            self.totalHammingDistanceHelper(nums, i, result, index_set)

    def getHammingDistance(self, num1, num2):
        distance = 0
        while num1 != 0 and num2 != 0:
            if num1 % 2 != num2 % 2:
                distance += 1
            num1 /= 2
            num2 /= 2

        while num1 != 0:
            if num1 % 2 == 1:
                distance += 1
            num1 /= 2

        while num2 != 0:
            if num2 % 2 == 1:
                distance += 1
            num2 /= 2

        return distance

def hamming_distance(num1, num2):
    distance = 0
    xor = num1 ^ num2
    while xor != 0:
        if xor & 1 == 1:
            distance += 1
        xor >>= 1

    return distance

NOTE

• 0 ^ 0 = 1 1 ^ 0 = 1 1 ^ 1 = 0