Problem Explanation

In this problem, we are given an array of integers and we are required to compute the total Hamming distance between all pairs of the given numbers. Hamming distance is defined as the number of positions at which the corresponding bits are different in the binary representation of two numbers.

For example, let's consider the numbers, 4, 14 and 2. Their binary representations are 0100, 1110 and 0010 respectively. To compute the total hamming distance, we perform an element-wise xor operation on each possible pair and count the number of '1's in the result. So, the total hamming distance will be HammingDistance(4,14) + HammingDistance(4,2) + HammingDistance(14,2) = 2 + 2 + 2 = 6.

Solution Approach

The given problem is a typical bitwise operation problem. A naive solution would be to calculate the Hamming distance for all pairs, but that would be very time-consuming and inefficient, particularly when the size of the input list is large. Instead, a more optimized approach will be used.

The optimized solution is to calculate the number of '1's and '0's in each bit position across all numbers. Since a '1' and a '0' at the same bit position contributes 1 towards the total Hamming distance, we multiply the count of '1's and '0's to get the total contribution from that bit position and do this for all bit positions (0 to 30) since a number can have at most 31 bits (0 to 30) as per the input constraint (0 to 10^9).

C++ Solution

1
2cpp
3class Solution {
4 public:
5  int totalHammingDistance(vector<int>& nums) {
6    int ans = 0;
7    int mask = 1;
8
9    for (int i = 0; i < 30; ++i) {
10      const int onesCount = count_if(begin(nums), end(nums),
11                                     [&mask](int num) { return num & mask; });
12      const int zerosCount = nums.size() - onesCount;
13      ans += onesCount * zerosCount;
14      mask <<= 1;
15    }
16
17    return ans;
18  }
19};

Python Solution

1
2python
3class Solution(object):
4  def totalHammingDistance(self, nums):
5    ans = 0
6    for i in range(30):
7      onesCount = sum(((num >> i) & 1) for num in nums)
8      zerosCount = len(nums) - onesCount
9      ans += onesCount * zerosCount
10    return ans

Java Solution

1
2java
3class Solution {
4    public int totalHammingDistance(int[] nums) {
5        int ans = 0;
6        for (int i = 0; i < 30; ++i) {
7            int onesCount = 0;
8            for (int num : nums) {
9                onesCount += (num >> i) & 1;
10            }
11            int zerosCount = nums.length - onesCount;
12            ans += onesCount * zerosCount;
13        }
14        return ans;
15    }
16}

JavaScript Solution

1
2javascript
3var totalHammingDistance = function(nums) {
4  let ans = 0;
5  for (let i = 0; i < 30; i++) {
6    let onesCount = 0;
7    for (const num of nums) {
8      onesCount += (num >> i) & 1;
9    }
10    const zerosCount = nums.length - onesCount;
11    ans += onesCount * zerosCount;
12  }
13  return ans;
14};

C# Solution

1
2csharp
3public class Solution {
4    public int TotalHammingDistance(int[] nums) {
5        int ans = 0;
6        for (int i = 0; i < 30; ++i) {
7            int onesCount = 0;
8            foreach (int num in nums) {
9                onesCount += (num >> i) & 1;
10            }
11            int zerosCount = nums.Length - onesCount;
12            ans += onesCount * zerosCount;
13        }
14        return ans;
15    }
16}

In all of the above solutions, we iterate through each number in the array for each bit from 0 to 30. The time complexity is O(30n) which reduces to O(n), where n is the number of integers in the array. Since we don't use any additional data structure, the space complexity is O(1).# Ruby Solution

While Ruby may not be as popular a language as Python, JavaScript, C++, Java, or C#, it is still very useful to know. Here is a solution to this problem implemented in Ruby:

1
2ruby
3class Solution
4  def total_hamming_distance(nums)
5    ans = 0
6    for i in 0...30
7      ones_count = 0
8      nums.each do |num|
9        ones_count += (num >> i) & 1
10      end
11      zeros_count = nums.length - ones_count
12      ans += ones_count * zeros_count
13    end
14    ans
15  end
16end

In this solution, we are relying on the >> operator to shift the bits of the number to the right. At each iteration, we use bitwise AND to count the number of '1's in the array for the current bit. We also calculate the number of '0's. Finally, we add the product of ones_count and zeros_count to the final result. This process repeats for each bit in the defined range.

This solution has a time complexity of O(n), where n is the number of elements in the array nums. And its space complexity is O(1) as it doesn't use additional space that grows with the input.

The solutions provided here for Python, JavaScript, C++, Java, C#, and Ruby solve the problem efficiently by calculating the number of 1's and 0's in each bit across all numbers. The computed Hamming distance is a result of the product of these counts, summing the computed values for all bit positions.