Domain 2MediumCORE

Total Hamming Distance

We are given an array of integers nums. The goal is to calculate the sum of Hamming distances for every unique pair in that array.

Domain: Medium•Updated: 2026-08-31
#Algorithms#LeetCode#qwen3.5:9b#Bit Manipulation

477. Total Hamming Distance

Model: qwen3.5:9b
Topics: Bit Manipulation
FAANG asked: 1
Acceptance rate: 50.7%


Problem Breakdown

We are given an array of integers nums. The goal is to calculate the sum of Hamming distances for every unique pair in that array.

Inputs: A list of non-negative integers (0 to 10910^9). Output: An integer representing the total count of differing bits across all pairs. Constraints & Edge Cases:

  • Array Length (NN): Up to 10410^4. This suggests an O(N)O(N) or O(Nlog⁡N)O(N \log N) solution is preferred over quadratic time, though a naive bit-count per pair might pass in C++, Python’s overhead makes optimization necessary.
  • Value Range: Values up to 10910^9 fit within 32 bits (since 230>1092^{30} > 10^9). We don’t need arbitrary precision logic beyond standard integer types, but we must check enough bit positions to cover the maximum value present in nums.
  • Empty/Single Element: If there are no pairs (N<2N < 2), the answer is trivially 00.

Intuition

A brute-force approach would iterate through every pair (i,j)(i, j) where i≠ji \neq j, compute their Hamming distance (using XOR and bit count), and sum them up.

  • Complexity: This results in roughly N(N−1)2\frac{N(N-1)}{2} pairs. For each pair, we check ~30 bits. Total complexity: O(N2⋅B)O(N^2 \cdot B). With N=104N=10^4, N2=108N^2 = 10^8, which risks Time Limit Exceeded (TLE), especially in interpreted languages like Python.

Key Insight: The Hamming distance is defined bitwise. The total sum of distances across all pairs can be decomposed by bit position. For any specific bit column (e.g., the kk-th bit from right):

  1. If a number has a 0 at this position and another has a 1, they contribute exactly 1 to the distance for that pair.
  2. Pairs where both have 0 or both have 1 contribute 0.

Therefore, we don’t need to compare numbers against each other directly. We just count how many numbers have a 1 at bit position kk (let’s call this count_ones). Consequently, the number of elements with a 0 is (N - count_ones). The contribution of this specific bit column to the total distance is simply: count_ones * (N - count_ones).

We sum this product across all relevant bit positions. This reduces complexity from O(N2)O(N^2) to O(N⋅B)O(N \cdot B), where BB is a small constant (~30).

Approach

  1. Initialize total_distance to 0.
  2. Determine the number of bits we need to check (e.g., up to bit index 30 covers all inputs ≤109\le 10^9, or iterate until max value in array is exhausted). A fixed range like range(32) is safe and efficient for this constraint.
  3. Iterate through each bit position ii from 0 to 31:
    • Count how many numbers have the ii-th bit set (count_ones). This can be done using bitwise AND with (1 << i).
  4. Calculate zeros = N - count_ones.
  5. Add count_ones * zeros to total_distance.
  6. Return total_distance.

Complexity Analysis

  • Time: O(N⋅B)O(N \cdot B), where NN is the number of elements and BB is the bit width (constant ~32). Effectively linear time relative to input size.
  • Space: O(1)O(1). We only use a few integer variables for counting; no additional data structures are required.

Solution

def totalHammingDistance(nums):
    """
    Calculates the sum of Hamming distances between all pairs in nums.
    
    Args:
        nums (List[int]): List of non-negative integers.
        
    Returns:
        int: Total Hamming distance for all unique pairs.
    """
    if not nums or len(nums) < 2:
        return 0
    
    total_distance = 0
    n = len(nums)
    
    # Iterate over bit positions sufficient to cover max value (10^9 fits in ~30 bits).
    # Using range(32) covers standard integer sizes safely.
    for i in range(32): 
        count_ones = 0
        
        # Count how many numbers have the current bit set
        mask = 1 << i
        for num in nums:
            if (num & mask) != 0:
                count_ones += 1
                
        # Contribution of this bit position to total distance is 
        # pairs formed by one '1' and one '0'.
        zeros_count = n - count_ones
        total_distance += count_ones * zeros_count
        
    return total_distance

Edge Cases Handled

  • Empty or Single Element Array: The function returns 0 immediately if N<2N < 2, as no pairs exist.
  • All Identical Numbers: If all numbers are the same, every bit column will have either count_ones = N (zeros=0) or count_zeros = N. In both cases, product is 0. Correctly returns 0 distance.
  • Maximum Value (10910^9): The loop range of 32 bits ensures we cover the binary representation of 10910^9 without overflow issues (Python handles large integers automatically).
  • Duplicates: Handled naturally by counting occurrences; duplicates simply increment count_ones or zeros_count, affecting the product calculation correctly.