Question

477. Total Hamming Distance

中文文档

Description

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

Solution 1

class Solution:
  def totalHammingDistance(self, nums: List[int]) -> int:
    ans = 0
    for i in range(31):
      a = b = 0
      for v in nums:
        t = (v >> i) & 1
        if t:
          a += 1
        else:
          b += 1
      ans += a * b
    return ans

class Solution {
  public int totalHammingDistance(int[] nums) {
    int ans = 0;
    for (int i = 0; i < 31; ++i) {
      int a = 0, b = 0;
      for (int v : nums) {
        int t = (v >> i) & 1;
        a += t;
        b += t ^ 1;
      }
      ans += a * b;
    }
    return ans;
  }
}

class Solution {
public:
  int totalHammingDistance(vector<int>& nums) {
    int ans = 0;
    for (int i = 0; i < 31; ++i) {
      int a = 0, b = 0;
      for (int& v : nums) {
        int t = (v >> i) & 1;
        a += t;
        b += t ^ 1;
      }
      ans += a * b;
    }
    return ans;
  }
};

func totalHammingDistance(nums []int) int {
  ans := 0
  for i := 0; i < 31; i++ {
    a, b := 0, 0
    for _, v := range nums {
      t := (v >> i) & 1
      a += t
      b += t ^ 1
    }
    ans += a * b
  }
  return ans
}