Problem Description
Given an integer array nums, return the sum of Hamming distances between all pairs of integers in nums. The Hamming distance between two integers is the number of positions at which the corresponding bits are different.
Key Insights
- The Hamming distance can be calculated by comparing each bit position of the integers.
- For each bit position, count how many numbers have that bit set to 1 and how many have it set to 0.
- The contribution to the Hamming distance from a specific bit position can be calculated as the product of counts of 1s and 0s at that position.
- This approach allows for a more efficient computation than directly comparing each pair of integers.
Space and Time Complexity
Time Complexity: O(32 * n) = O(n) since we iterate over each bit position (up to 32 for 32-bit integers) and through the array of integers. Space Complexity: O(1) as we only use a constant amount of space for counters.
Solution
To calculate the total Hamming distance, we will iterate over each bit position (0 to 31). For each bit, we count how many numbers in the array have that bit set to 1 and how many have it set to 0. The total contribution to the Hamming distance from this bit position is the product of these two counts. We sum this contribution for all bit positions to get the final result.