How do you solve Total Hamming Distance on LeetCode?

Total Hamming Distance (LeetCode #477) can be solved using Brute Force or Optimal Solution. The optimal approach is Optimal Solution with O(n) time complexity and O(1) space complexity. Key insight: The Hamming distance is fundamentally about comparing bits, so understanding bit manipulation is crucial.

What is the brute force solution for Total Hamming Distance?

The brute force approach for Total Hamming Distance is Brute Force, with O(n²) time complexity and O(1) space complexity. The brute force approach calculates the Hamming distance for every possible pair of integers in the array. This is straightforward but inefficient for larger arrays since it checks each pair individually. The optimal Optimal Solution approach improves this to O(n).

What algorithm or data structure is used to solve Total Hamming Distance?

Total Hamming Distance uses the following concepts: Array, Math, Bit Manipulation. The recommended patterns to study are: Bit Manipulation, Array.

What are the interview tips for Total Hamming Distance?

Always start with a brute-force solution to understand the problem better before optimizing. Explain your thought process clearly when transitioning from brute-force to an optimal solution. Practice bit manipulation problems to become more comfortable with operations like shifts and masks.

What are common mistakes when solving Total Hamming Distance?

Forgetting to account for all bit positions (0 to 31) in the optimal approach. Not using bitwise operations correctly, which can lead to incorrect Hamming distance calculations.

#477

Total Hamming Distance

Medium

ArrayMathBit ManipulationBit ManipulationArray

LeetCode ↗

Approaches

Brute ForceOptimal

Complexity Comparison

	Brute Force	Optimal Solution★
Time	O(n²)	O(n)
Space	O(1)	O(1)

💡

Intuition

Time O(n)Space O(1)

Instead of calculating the Hamming distance for every pair, we can count how many numbers have a bit set at each position. This allows us to compute the contribution of each bit position to the total Hamming distance more efficiently.

⚙️

Algorithm

5 steps

1Step 1: Initialize a variable to store the total Hamming distance.
2Step 2: Iterate through each bit position from 0 to 31 (since nums[i] <= 10^9 fits in 32 bits).
3Step 3: For each bit position, count how many numbers have that bit set (1) and how many do not (0).
4Step 4: The contribution to the total Hamming distance from this bit position is the product of the count of 1s and 0s.
5Step 5: Add this contribution to the total.

solution.py13 lines

1# Full working Python code
2
3def totalHammingDistance(nums):
4    total = 0
5    n = len(nums)
6    for i in range(32):
7        count_one = sum((num >> i) & 1 for num in nums)
8        count_zero = n - count_one
9        total += count_one * count_zero
10    return total
11
12# Example usage
13print(totalHammingDistance([4, 14, 2]))  # Output: 6

ℹ

Complexity note: The time complexity is O(n) because we iterate through the array a constant number of times (32 for each bit position). The space complexity is O(1) since we only use a fixed amount of extra space.

1The Hamming distance is fundamentally about comparing bits, so understanding bit manipulation is crucial.
2Counting contributions from each bit position is more efficient than brute-force pairwise comparisons.

Solutions and explanations are original Tejav content. Problem titles © LeetCode — use the LeetCode button above for the full problem statement.