Total Hamming Distance - Practice Coding Problems

Total Hamming Distance - Problem

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

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

Example: For array [4, 14, 2], we need to find Hamming distances between all pairs: (4,14), (4,2), and (14,2), then sum them up.

Input & Output

Example 1 — Basic Case

$ Input: nums = [4, 14, 2]

› Output: 6

💡 Note: Hamming distances: H(4,14)=2 (100⊕1110=1010), H(4,2)=2 (100⊕010=110), H(14,2)=2 (1110⊕010=1100). Total = 2+2+2 = 6

Example 2 — Minimum Size

$ Input: nums = [4, 14]

› Output: 2

💡 Note: Only one pair: H(4,14) = 2 (binary 100 vs 1110 differ in 2 positions)

Example 3 — Same Numbers

$ Input: nums = [1, 1, 1]

› Output: 0

💡 Note: All numbers are identical, so Hamming distance between any pair is 0

Constraints

1 ≤ nums.length ≤ 10⁴
0 ≤ nums[i] ≤ 10⁹

Visualization

Tap to expand

Understanding the Visualization

Input

Array of integers to compare

Process

Calculate Hamming distance between all pairs

Output

Sum of all pairwise distances

Key Takeaway

🎯 Key Insight: Instead of comparing n² pairs, analyze each bit position once to count differing pairs mathematically

Asked in

f Facebook 25 G Google 20 M Microsoft 15

The key insight is to avoid O(n²) pair comparisons by analyzing each bit position independently. For each bit position, count numbers with bit=1 vs bit=0, then calculate contribution using ones × zeros. Best approach is bit manipulation with Time: O(n), Space: O(1).

Common Approaches

Approach	Time	Space	Notes
✓ Bit Position Analysis	O(n × 32)	O(1)	Count contributions of each bit position across all numbers
Brute Force - Compare All Pairs	O(n² × log M)	O(1)	Calculate Hamming distance for every pair of numbers and sum them up

Bit Position Analysis — Algorithm Steps

Step 1: For each bit position (0 to 31 for 32-bit integers)
Step 2: Count how many numbers have bit=1 at this position
Step 3: Calculate contribution: ones × (n - ones) × 2^position
Step 4: Sum contributions from all bit positions

Visualization

Tap to expand

Step-by-Step Walkthrough

Bit Analysis

For each bit position, count 1s vs 0s

Calculate Contribution

ones × zeros gives pairs that differ

Sum All Positions

Add contributions from all bit positions

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int solution(int* nums, int numsSize) {
    int total = 0;
    
    // Check each bit position (0 to 31 for 32-bit integers)
    for (int i = 0; i < 32; i++) {
        int ones = 0;
        // Count how many numbers have bit i set to 1
        for (int j = 0; j < numsSize; j++) {
            if (nums[j] & (1 << i)) {
                ones++;
            }
        }
        
        int zeros = numsSize - ones;
        // Each pair of (1,0) contributes 1 to hamming distance at this position
        total += ones * zeros;
    }
    
    return total;
}

int main() {
    char line[10000];
    fgets(line, sizeof(line), stdin);
    
    int nums[1000];
    int count = 0;
    
    char* token = strtok(line + 1, ",]");
    while (token != NULL) {
        nums[count++] = atoi(token);
        token = strtok(NULL, ",]");
    }
    
    int result = solution(nums, count);
    printf("%d\n", result);
    
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n × 32)

For each of 32 bit positions, we scan through n numbers once

✓ Linear Growth

Space Complexity

O(1)

Only using constant extra variables for counting

✓ Linear Space

28.5K Views

Medium Frequency

~25 min Avg. Time

892 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Bit Position Analysis — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler