Total Hamming Distance — LeetCode 477 Python Solution

The problem

The Hamming distance between two integers is the number of positions at which the corresponding bits are different. Given an integer array nums, return the sum of Hamming distances between all the pairs of the integers in nums.

Example

Input

nums = [4,14,2]

Output

6

Explanation

In binary representation, the 4 is 0100, 14 is 1110, and 2 is 0010 (just

Python solution

class Solution:
    def totalHammingDistance(self, nums: List[int]) -> int:
        ans, n = 0, len(nums)
        for i in range(32):
            a = sum(x >> i & 1 for x in nums)
            b = n - a
            ans += a * b
        return ans

Complexity

Pattern: Bit Manipulation

Use XOR, masks and the low-bit trick to replace whole data structures with an integer. LeetCode 477. Total Hamming Distance is filed here on both counts: the reference solution below belongs to the algorithm family this hub collects, and LeetCode tags it Bit Manipulation.

The bit manipulation guide has the Python template for the pattern and the 194 LeetCode problems that use it.

Related problems