Maximum Hamming Distances - Practice Coding Problems

Maximum Hamming Distances - Problem

Given an array nums and an integer m, with each element nums[i] satisfying 0 ≤ nums[i] < 2^m, return an array answer.

The answer array should be of the same length as nums, where each element answer[i] represents the maximum Hamming distance between nums[i] and any other element nums[j] in the array.

The Hamming distance between two binary integers is defined as the number of positions at which the corresponding bits differ (add leading zeroes if needed).

Input & Output

Example 1 — Basic Case

$ Input: nums = [3,1,4,2], m = 3

› Output: [3,3,3,3]

💡 Note: For nums[0]=3 (011): max distance is with nums[2]=4 (100), differing in 3 positions. Each number can achieve distance 3 with some other number.

Example 2 — Small Array

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

› Output: [1,1]

💡 Note: 1 (binary: 1) and 0 (binary: 0) differ in 1 position, so maximum distance for both is 1.

Example 3 — Same Numbers

$ Input: nums = [2,2,2], m = 2

› Output: [0,0,0]

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

Constraints

2 ≤ nums.length ≤ 10⁴
1 ≤ m ≤ 20
0 ≤ nums[i] < 2^m

Visualization

Tap to expand

Understanding the Visualization

Input Array

Array of numbers with their binary representations

Compare Pairs

For each number, find maximum Hamming distance with others

Output Result

Array showing maximum distance for each position

Key Takeaway

🎯 Key Insight: Maximum Hamming distance occurs when two numbers differ in the most bit positions

Asked in

G Google 45 f Meta 32 a Amazon 28 M Microsoft 23

The key insight is that Hamming distance is calculated by XORing two numbers and counting set bits. The brute force approach compares every pair to find maximum distance for each number. Time: O(n²×m), Space: O(1). Advanced optimizations can analyze bit patterns but still require pairwise comparisons for correctness.

Common Approaches

Approach	Time	Space	Notes
✓ Optimized Bit Analysis	O(n² × m)	O(m)	Analyze bit positions across all numbers to find optimal pairs more efficiently
Brute Force	O(n² × m)	O(1)	Compare each number with every other number to find maximum Hamming distance
Bit Manipulation Optimization	O(n² × m)	O(1)	Use bit patterns to find the number that maximally differs from each element

Optimized Bit Analysis — Algorithm Steps

Step 1: For each bit position, count how many numbers have 0 vs 1
Step 2: For each number, calculate potential maximum by flipping bits optimally
Step 3: Find actual maximum by checking against real numbers in array

Visualization

Tap to expand

Step-by-Step Walkthrough

Count Bit Positions

For each bit position, count 0s and 1s across all numbers

Analyze Patterns

Understand which numbers have opposite bit patterns

Find Maximum

Still need to check all pairs for actual maximum

Code -

solution.c — C

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

int popcount(int n) {
    int count = 0;
    while (n) {
        count++;
        n &= (n - 1);
    }
    return count;
}

int* solution(int* nums, int numsSize, int m, int* returnSize) {
    *returnSize = numsSize;
    int* answer = (int*)malloc(numsSize * sizeof(int));
    
    // Count bits at each position
    int bitCounts[32][2] = {0}; // [count of 0s, count of 1s]
    
    for (int i = 0; i < numsSize; i++) {
        for (int bitPos = 0; bitPos < m; bitPos++) {
            if ((nums[i] >> bitPos) & 1) {
                bitCounts[bitPos][1]++;
            } else {
                bitCounts[bitPos][0]++;
            }
        }
    }
    
    // For each number, find maximum Hamming distance
    for (int i = 0; i < numsSize; i++) {
        int maxDist = 0;
        for (int j = 0; j < numsSize; j++) {
            if (i != j) {
                int hammingDist = popcount(nums[i] ^ nums[j]);
                if (hammingDist > maxDist) {
                    maxDist = hammingDist;
                }
            }
        }
        answer[i] = maxDist;
    }
    
    return answer;
}

int main() {
    char line[1000];
    fgets(line, sizeof(line), stdin);
    
    // Parse array
    int nums[100];
    int numsSize = 0;
    char* token = strtok(line, "[,]");
    while (token != NULL) {
        if (strlen(token) > 0 && token[0] != '\n') {
            nums[numsSize++] = atoi(token);
        }
        token = strtok(NULL, "[,]");
    }
    
    int m;
    scanf("%d", &m);
    
    int returnSize;
    int* result = solution(nums, numsSize, m, &returnSize);
    
    printf("[");
    for (int i = 0; i < returnSize; i++) {
        printf("%d", result[i]);
        if (i < returnSize - 1) printf(",");
    }
    printf("]\n");
    
    free(result);
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n² × m)

Still need O(n²) comparisons to find actual maximum in the given array

⚠ Quadratic Growth

Space Complexity

O(m)

Need to store bit counts for each of the m bit positions

✓ Linear Space

23.4K Views

Medium Frequency

~25 min Avg. Time

847 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

Optimized Bit Analysis — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler