algoadvance

Given an integer array nums, return the sum of Hamming distances between all the pairs of the integers in the array.

The Hamming distance between two integers is the number of positions at which the corresponding bits are different.

Example 1:

Input: nums = [4, 14, 2]
Output: 6
Explanation: There are 3 pairs:
(4, 14) with Hamming distance 2,
(4, 2) with Hamming distance 2,
(14, 2) with Hamming distance 2.
So the total Hamming distance is 2 + 2 + 2 = 6.

Example 2:

Input: nums = [4,14,4]
Output: 4

Constraints:

• 1 <= nums.length <= 10^4
• 0 <= nums[i] <= 10^9

Clarifying Questions

1. Input Range and Constraints Clarification:
   • Can the array contain negative integers, or is it strictly non-negative?
     • According to the problem constraints, the numbers are non-negative.
2. Output Specification:
   • We should return the sum of Hamming distances for all pairs in the array, correct?
     • That’s correct.
3. Bit Length:
   • Since the maximum number could be as large as (10^9), do we consider all 32 bits of an integer?
     • Yes, we should consider up to 32 bits for the given constraint.

Strategy

To solve this problem efficiently, calculating the Hamming distance for each pair of numbers traditionally would be computationally expensive ((O(n^2 \cdot 32))). Instead, we can use the following optimized approach:

1. Bitwise Counting Approach:
   • For each bit position (0 to 31), count the number of integers that have the bit set among all integers in the array.
   • For each bit position, if k numbers have the bit set, and n is the total number of numbers, then (n - k) numbers have the bit unset.
   • The contribution to the Hamming distance for this bit position is k * (n - k).

This approach has a time complexity of (O(n \cdot 32)) which is linear in terms of the number of elements, and hence, should be efficient given the constraints.

Code

def totalHammingDistance(nums):
    total = 0
    n = len(nums)
    
    for i in range(32):
        bit_count = 0
        for num in nums:
            bit_count += (num >> i) & 1
        
        total += bit_count * (n - bit_count)
    
    return total

# Example usage:
nums = [4, 14, 2]
print(totalHammingDistance(nums))  # Output: 6

Time Complexity

• Time Complexity: (O(n \cdot 32) = O(n)), where (n) is the length of the input array due to the bitwise operations over 32 bits per array element.
• Space Complexity: (O(1)), as the space used does not grow with the input size and is constant.

This solution ensures that we efficiently compute the total Hamming distance across all pairs in the given integer array.

Try our interview co-pilot at AlgoAdvance.com

• Got blindsided by a question you didn’t expect?

• Spend too much time studying?

• Or simply don’t have the time to go over all 3000 questions?