477. Total Hamming Distance

Problem Statement

link: LeetCode.cn LeetCode 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

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.

Solution Approach

The solution counts the number of 1s and 0s at each bit position across all numbers in the array and calculates the total Hamming distance by summing the product of these counts for each bit position.

Algorithm

1. Bitwise Counting: For each bit position (0 to 29), count how many numbers in the array have a 1 at that position.
2. Pair Calculation: For each bit position, compute the number of pairs with different bits (one 0 and one 1) by multiplying the count of 1s by the count of 0s.
3. Summation: Sum the products from all bit positions to get the total Hamming distance for all pairs in the array.

Implement

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

    
    

Twitter  facebook  Email