Skip to content

477. Total Hamming Distance 👍

  • Time: $O(30n) = O(n)$
  • Space: $O(1)$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
class Solution {
 public:
  int totalHammingDistance(vector<int>& nums) {
    constexpr int kMaxMask = 1 << 30;
    int ans = 0;

    for (int mask = 1; mask < kMaxMask; mask <<= 1) {
      const int ones =
          ranges::count_if(nums, [mask](int num) { return num & mask; });
      const int zeros = nums.size() - ones;
      ans += ones * zeros;
    }

    return ans;
  }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
class Solution {
  public int totalHammingDistance(int[] nums) {
    final int kMaxBit = 30;
    int ans = 0;

    for (int i = 0; i < kMaxBit; ++i) {
      final int mask = 1 << i;
      final int ones = (int) Arrays.stream(nums).filter(num -> (num & mask) > 0).count();
      final int zeros = nums.length - ones;
      ans += ones * zeros;
    }

    return ans;
  }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
class Solution:
  def totalHammingDistance(self, nums: list[int]) -> int:
    kMaxBit = 30
    ans = 0

    for i in range(kMaxBit):
      ones = sum(num & (1 << i) > 0 for num in nums)
      zeros = len(nums) - ones
      ans += ones * zeros

    return ans