Skip to content

477. Total Hamming Distance

Array Math Bit Manipulation

Problem - Total Hamming Distance

Medium

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 1:

Input: nums = [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).
The answer will be:
HammingDistance(4, 14) + HammingDistance(4, 2) + HammingDistance(14, 2) = 2 + 2 + 2 = 6.

Example 2:

Input: nums = [4,14,4]
Output: 4

 

Constraints:

  • 1 <= nums.length <= 104
  • 0 <= nums[i] <= 109
  • The answer for the given input will fit in a 32-bit integer.

Solutions

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
class Solution:
    def totalHammingDistance(self, nums: List[int]) -> int:
        n = len(nums)
        result = 0

        max_num = max(nums)
        max_bits = len(format(max_num, 'b'))

        for i in range(max_bits):
            one_bits = sum(x >> i & 1 for x in nums)
            zero_bits = n - one_bits
            result += one_bits * zero_bits

        return result

Submission Stats:

  • Runtime: 169 ms (64.34%)
  • Memory: 18.8 MB (77.76%)