We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Total Hamming Distance

Number: 477

Difficulty: Medium

Paid? No

Companies: Microsoft, Meta

Problem Description

Given an integer array nums, compute the sum of Hamming distances between all pairs of the integers in nums. The Hamming distance between two integers is the number of positions at which the corresponding bits are different.

Key Insights

  • Instead of comparing every pair (which would be O(n^2)), consider each bit position independently.
  • For each bit position, count the number of integers with a 1 and with a 0.
  • The contribution of each bit to the Hamming distance is count_ones * count_zeroes.
  • Sum the contributions of all 32 possible bit positions to get the final answer.

Space and Time Complexity

Time Complexity: O(n * 32) = O(n)
Space Complexity: O(1)

Solution

The main idea is to calculate the contribution of each bit position separately. For each bit position (from 0 to 31), we traverse the array and count how many numbers have that bit set (1) and how many do not (0). The number of pair differences at that position is the product of these two counts. By summing the contributions across all bit positions, we get the total Hamming distance. This approach leverages bit manipulation and avoids a direct O(n^2) pairwise comparison.

Code Solutions

# Calculate total Hamming distance using bit manipulation
def totalHammingDistance(nums):
    total_distance = 0
    n = len(nums)
    # Loop over each bit position (0 to 31)
    for bit in range(32):
        count_ones = 0
        # Count how many numbers have the bit set at current position
        for num in nums:
            if (num >> bit) & 1:
                count_ones += 1
        count_zeroes = n - count_ones  # Numbers that have the bit not set
        # Each pair contributes 1 to Hamming distance when bits differ
        total_distance += count_ones * count_zeroes
    return total_distance

# Example usage:
nums = [4, 14, 2]
print(totalHammingDistance(nums))  # Expected output: 6
← Back to All Questions