477. Total Hamming Distance LeetCode Solution

In this guide, you will get 477. Total Hamming Distance LeetCode Solution with the best time and space complexity. The solution to Total Hamming Distance problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.

Problem Statement
Complexity Analysis
Total Hamming Distance solution in C++
Total Hamming Distance solution in Java
Total Hamming Distance solution in Python
Additional Resources

477. Total Hamming Distance LeetCode Solution image

Problem Statement of Total Hamming Distance

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.

Complexity Analysis

Time Complexity: O(30n) = O(n)
Space Complexity: O(1)

477. Total Hamming Distance LeetCode Solution in C++

class Solution {
 public:
  int totalHammingDistance(vector<int>& nums) {
    constexpr int maxMask = 1 << 30;
    int ans = 0;

    for (int mask = 1; mask < maxMask; 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;
  }
};
/* code provided by PROGIEZ */

477. Total Hamming Distance LeetCode Solution in Java

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;
  }
}
// code provided by PROGIEZ

477. Total Hamming Distance LeetCode Solution in Python

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
 # code by PROGIEZ