Solution Explanation: Total Hamming Distance

This problem asks for the sum of Hamming distances between all pairs of integers in an input array. The Hamming distance between two integers is the number of positions at which their corresponding bits differ.

Approach:

The naive approach of calculating the Hamming distance for every pair of numbers in the array would have a time complexity of O(n^2 * log M), where n is the length of the array and M is the maximum value in the array (log M accounts for the bitwise comparisons). This is inefficient for larger arrays.

A more efficient approach leverages bit manipulation and exploits the pattern in calculating Hamming distances. Instead of comparing pairs directly, we iterate through each bit position (0 to 31 for 32-bit integers). For each bit position:

1. Count set bits: Count the number of integers in the array that have a '1' in that bit position. Let's call this count a.

2. Count unset bits: The number of integers with a '0' in that bit position is simply the total number of integers (n) minus a, which we'll call b.

3. Calculate Hamming distance for the bit: The contribution to the total Hamming distance from this bit position is a * b. This is because each '1' bit contributes to a Hamming distance with each '0' bit.

4. Sum up contributions: Repeat steps 1-3 for all 32 bit positions and sum up the contributions to obtain the final total Hamming distance.

Time and Space Complexity:

• Time Complexity: O(n * k), where n is the length of the array and k is the number of bits (32 in this case). This is because we iterate through the array once for each bit. This is significantly better than the O(n^2 * log M) of the naive approach.

• Space Complexity: O(1). The algorithm uses only a constant amount of extra space.

Code Implementation (Python):

class Solution:
    def totalHammingDistance(self, nums: List[int]) -> int:
        ans, n = 0, len(nums)
        for i in range(32):  # Iterate through each bit position
            a = sum(x >> i & 1 for x in nums)  # Count set bits in the ith position
            b = n - a  # Count unset bits
            ans += a * b  # Add the contribution to the total Hamming distance
        return ans
 

Code Implementation in other languages are similar in structure and logic. They all follow the same approach of iterating through bits and efficiently calculating the Hamming distance contribution from each bit position. The only differences would be syntax specific to each language. The core algorithm remains consistent across all implementations.