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 ).
Output: An integer representing the total count of differing bits across all pairs.
Constraints & Edge Cases:
- Array Length (): Up to . This suggests an or 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 fit within 32 bits (since ). 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 (), the answer is trivially .
Intuition
A brute-force approach would iterate through every pair where , compute their Hamming distance (using XOR and bit count), and sum them up.
- Complexity: This results in roughly pairs. For each pair, we check ~30 bits. Total complexity: . With , , 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 -th bit from right):
- If a number has a
0at this position and another has a1, they contribute exactly 1 to the distance for that pair. - Pairs where both have
0or both have1contribute 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 (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 to , where is a small constant (~30).
Approach
- Initialize
total_distanceto 0. - Determine the number of bits we need to check (e.g., up to bit index 30 covers all inputs , or iterate until max value in array is exhausted). A fixed range like
range(32)is safe and efficient for this constraint. - Iterate through each bit position from 0 to 31:
- Count how many numbers have the -th bit set (
count_ones). This can be done using bitwise AND with(1 << i).
- Count how many numbers have the -th bit set (
- Calculate
zeros = N - count_ones. - Add
count_ones * zerostototal_distance. - Return
total_distance.
Complexity Analysis
- Time: , where is the number of elements and is the bit width (constant ~32). Effectively linear time relative to input size.
- Space: . 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
0immediately if , as no pairs exist. - All Identical Numbers: If all numbers are the same, every bit column will have either
count_ones = N(zeros=0) orcount_zeros = N. In both cases, product is 0. Correctly returns 0 distance. - Maximum Value (): The loop range of 32 bits ensures we cover the binary representation of without overflow issues (Python handles large integers automatically).
- Duplicates: Handled naturally by counting occurrences; duplicates simply increment
count_onesorzeros_count, affecting the product calculation correctly.