We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Maximum Hamming Distances

Number: 3449

Difficulty: Hard

Paid? Yes

Companies: N/A

Problem Description

Given an array nums and an integer m, where each element in nums is within the range [0, 2^m - 1], return an array answer of the same length. For each index i, answer[i] is the maximum Hamming distance between nums[i] and any other element in nums. The Hamming distance is defined as the number of positions at which the corresponding bits differ (using m-bit binary representations with leading zeroes if necessary).

Key Insights

  • The maximum possible Hamming distance between two m-bit numbers is m.
  • For any number x, the maximum Hamming distance with a candidate y is obtained when y is as “distant” as possible from x in terms of bit differences.
  • Using the fact that Hamming(x, y) = m - Hamming(comp(x), y) where comp(x) is the m-bit complement of x, we can reframe the problem.
  • By computing, via multi-source BFS on the m-bit hypercube, the minimum Hamming distance from any vertex to the set of numbers in nums, we can then derive the maximum Hamming distance for each x as: m minus the distance for comp(x).

Space and Time Complexity

Time Complexity: O(2^m * m) – We perform BFS over all 2^m vertices, and each vertex has m neighbors. Space Complexity: O(2^m) – We use a distance array and queue of size 2^m.

Solution

We solve the problem by performing a multi-source BFS on the m-bit hypercube (vertices representing all numbers 0 to 2^m - 1). Start with all numbers in nums as sources (distance 0). For each vertex v in the hypercube, we determine the minimal number of bit flips required (its Hamming distance) to reach any number from nums.

For a given number x, consider its m-bit complement, computed as x XOR (2^m - 1). The Hamming distance between x and any y equals m minus the Hamming distance between comp(x) and y. Hence, the maximum Hamming distance achievable for x is m minus the minimal distance computed for its complement vertex.

Data Structures and Techniques:

  • Use an array of size 2^m to store the minimum distance from each vertex to any number in nums.
  • Employ a multi-source BFS to compute these distances over the hypercube.
  • Finally, using the complement trick, compute the maximum Hamming distance for each x.

Code Solutions

from collections import deque

def maximumHammingDistances(nums, m):
    max_val = (1 << m) - 1  # Maximum m-bit number (all bits set)
    size = 1 << m           # Total vertices in m-bit hypercube
    dist = [float('inf')] * size

    # Initialize multi-source BFS with vertices from nums
    queue = deque()
    for num in nums:
        if dist[num] == 0:
            continue
        dist[num] = 0
        queue.append(num)

    # Multi-source BFS over hypercube graph
    while queue:
        cur = queue.popleft()
        cur_dist = dist[cur]
        # Explore neighbors by flipping each bit
        for i in range(m):
            neighbor = cur ^ (1 << i)
            if dist[neighbor] > cur_dist + 1:
                dist[neighbor] = cur_dist + 1
                queue.append(neighbor)
    
    # For each number, maximum Hamming distance = m - (min distance from complement)
    result = []
    for num in nums:
        complement = num ^ max_val
        result.append(m - dist[complement])
    return result

# Example usage:
print(maximumHammingDistances([9,12,9,11], 4))  # Expected output: [2, 3, 2, 3]
← Back to All Questions