Problem Description

You are given an array nums where each element satisfies 0 <= nums[i] < 2^m for a given integer m. Your task is to find the maximum Hamming distance for each element in the array.

For each element nums[i], you need to find the maximum Hamming distance between nums[i] and any other element nums[j] in the array (where i ≠ j).

The Hamming distance between two binary integers is the number of bit positions where the two numbers differ. When comparing, both numbers should be represented with the same number of bits (add leading zeros if necessary).

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

For example, if we have two numbers and their binary representations differ in 3 positions, their Hamming distance is 3. Since each number in the array is less than 2^m, they can all be represented using exactly m bits.

Flowchart Walkthrough

First, let's pin down the algorithm using the Flowchart. Here's a step-by-step walkthrough:

Is it a graph?

• Yes: We can model this problem as a graph where each number (from 0 to 2^m - 1) is a node, and edges connect numbers that differ by exactly one bit (Hamming distance of 1).

Is it a tree?

• No: The graph is not a tree. Numbers can be connected in cycles (e.g., flipping different bits can lead back to the same number through different paths).

Is the problem related to directed acyclic graphs?

• No: The graph is undirected (flipping a bit is reversible) and contains cycles.

Is the problem related to shortest paths?

• Yes: We need to find the shortest path from each number's complement to any number in the input array. The maximum Hamming distance equals m minus this shortest path.

Is the graph Weighted?

• No: Each edge has the same weight (1), representing a single bit flip.

BFS

• Yes: Since we have an unweighted graph and need to find shortest paths, BFS is the appropriate algorithm.

Conclusion: The flowchart leads us to use BFS. The solution treats the problem as finding shortest paths in an unweighted graph where:

• Nodes are all possible m-bit numbers
• Edges connect numbers differing by exactly one bit
• We use BFS starting from the input numbers to find distances to all reachable numbers
• The maximum Hamming distance for each number is m minus the distance to its complement

Intuition

The key insight is to think about the problem in reverse. Instead of directly finding the maximum Hamming distance for each number, we can leverage a clever observation: the number with maximum Hamming distance from x is its bitwise complement (all bits flipped).

For example, if we have x = 101 in binary, its complement is 010, and they differ in all 3 bit positions, giving the maximum possible Hamming distance of 3.

However, the complement might not exist in our input array. So we need to find the number in the array that is "closest" to the complement - this gives us the minimum distance from the complement to any array element. The maximum Hamming distance we seek is then m minus this minimum distance.

Why does this work? Consider any number y in the array:

• The Hamming distance between x and y equals the number of differing bits
• The complement of x (let's call it x') differs from x in all m bits
• If x' has distance d to y, then x has distance m - d to y

To find the minimum distance from each complement to array elements, we use BFS starting from all array elements simultaneously. We explore the "graph" where each number is connected to numbers that differ by exactly one bit. The BFS naturally finds shortest paths (minimum Hamming distances) from our starting points (array elements) to all reachable numbers.

The algorithm fills in distances layer by layer:

• Layer 0: The array elements themselves (distance 0)
• Layer 1: Numbers one bit flip away (distance 1)
• Layer 2: Numbers two bit flips away (distance 2)
• And so on...

Once we have these distances, for each element x, we look up the distance to its complement x ^ ((1 << m) - 1) and subtract from m to get the maximum Hamming distance.

Learn more about Breadth-First Search patterns.

Solution Approach

The implementation uses BFS to find minimum distances from array elements to all possible m-bit numbers, then uses these distances to compute maximum Hamming distances.

Step 1: Initialize Distance Array

dist = [-1] * (1 << m)
for x in nums:
    dist[x] = 0

We create a distance array of size 2^m to store the minimum distance from each number to any element in nums. Initially set all distances to -1 (unvisited), then mark all numbers in nums with distance 0.

Step 2: BFS Initialization

q = nums
k = 1

Start BFS with all numbers from nums as the initial layer (distance 0). Variable k tracks the current distance level.

Step 3: BFS Exploration

while q:
    t = []
    for x in q:
        for i in range(m):
            y = x ^ (1 << i)
            if dist[y] == -1:
                t.append(y)
                dist[y] = k
    q = t
    k += 1

For each number x in the current layer:

• Try flipping each of its m bits using x ^ (1 << i)
• If the resulting number y hasn't been visited (dist[y] == -1), mark it with distance k and add to the next layer
• Move to the next layer and increment the distance

The XOR operation x ^ (1 << i) flips the i-th bit of x. For example, if x = 5 (101) and i = 1, then 1 << 1 = 010, and 101 ^ 010 = 111 = 7.

Step 4: Calculate Maximum Hamming Distances

return [m - dist[x ^ ((1 << m) - 1)] for x in nums]

For each element x in nums:

• Calculate its complement: x ^ ((1 << m) - 1) where (1 << m) - 1 creates a mask of all 1s
• Look up the minimum distance to this complement: dist[x ^ ((1 << m) - 1)]
• The maximum Hamming distance is m minus this minimum distance

Time Complexity: O(2^m * m) - We potentially visit all 2^m numbers, and for each, we check m bit flips.

Space Complexity: O(2^m) - For the distance array storing distances to all possible m-bit numbers.

Example Walkthrough

Let's walk through a concrete example with nums = [1, 4, 5] and m = 3 (all numbers can be represented with 3 bits).

Step 1: Binary Representation

• 1 = 001
• 4 = 100
• 5 = 101

Step 2: Initialize Distance Array We create a distance array of size 2^3 = 8:

Index: 0   1   2   3   4   5   6   7
Value: 000 001 010 011 100 101 110 111
dist: [-1, 0, -1, -1, 0, 0, -1, -1]

Numbers 1, 4, and 5 (from our input) get distance 0.

Step 3: BFS Layer by Layer

Layer 0 (distance 0): Start with q = [1, 4, 5]

Processing Layer 0 to find Layer 1:

• From 1 (001): Flip each bit
  • Flip bit 0: 001 ^ 001 = 000 → Add to next layer, dist[0] = 1
  • Flip bit 1: 001 ^ 010 = 011 → Add to next layer, dist[3] = 1
  • Flip bit 2: 001 ^ 100 = 101 → Already visited (dist[5] = 0)
• From 4 (100): Flip each bit
  • Flip bit 0: 100 ^ 001 = 101 → Already visited
  • Flip bit 1: 100 ^ 010 = 110 → Add to next layer, dist[6] = 1
  • Flip bit 2: 100 ^ 100 = 000 → Already visited (dist[0] = 1)
• From 5 (101): Flip each bit
  • Flip bit 0: 101 ^ 001 = 100 → Already visited
  • Flip bit 1: 101 ^ 010 = 111 → Add to next layer, dist[7] = 1
  • Flip bit 2: 101 ^ 100 = 001 → Already visited

Layer 1 (distance 1): q = [0, 3, 6, 7]

dist: [1, 0, -1, 1, 0, 0, 1, 1]

Processing Layer 1 to find Layer 2:

• From 0 (000): Only unvisited neighbor is 010, so dist[2] = 2
• From 3 (011): 010 is already being set to 2
• From 6 (110): 010 is already being set to 2
• From 7 (111): 011 is already visited

Layer 2 (distance 2): q = [2]

Final dist: [1, 0, 2, 1, 0, 0, 1, 1]

Step 4: Calculate Maximum Hamming Distances

For each element, find its complement and look up the distance:

• For 1 (001):

  • Complement: 001 ^ 111 = 110 (which is 6)
  • dist[6] = 1
  • Maximum Hamming distance: 3 - 1 = 2

• For 4 (100):

  • Complement: 100 ^ 111 = 011 (which is 3)
  • dist[3] = 1
  • Maximum Hamming distance: 3 - 1 = 2

• For 5 (101):

  • Complement: 101 ^ 111 = 010 (which is 2)
  • dist[2] = 2
  • Maximum Hamming distance: 3 - 2 = 1

Verification:

• Max distance from 1 (001): Compare with 4 (100) → 2 differing bits ✓
• Max distance from 4 (100): Compare with 1 (001) → 2 differing bits ✓
• Max distance from 5 (101): Compare with both 1 (001) and 4 (100) → 1 differing bit each ✓

Final Answer: [2, 2, 1]

Solution Implementation

Time and Space Complexity

The time complexity is O(2^m × m) and the space complexity is O(2^m).

Time Complexity Analysis:

• The algorithm initializes a distance array dist of size 2^m with time O(2^m)
• It then performs a BFS traversal starting from all numbers in nums
• In the worst case, the BFS visits all 2^m possible values
• For each value visited, the algorithm checks all m bit positions to generate neighbors by flipping each bit (the inner loop for i in range(m))
• Each value is processed exactly once due to the dist[y] == -1 check
• Therefore, the total time complexity is O(2^m × m)

Space Complexity Analysis:

• The dist array stores distances for all 2^m possible values, requiring O(2^m) space
• The queue q can contain at most O(2^m) elements across all iterations
• The temporary list t also has maximum size O(2^m) in the worst case
• The overall space complexity is O(2^m)

Note: The reference answer states time complexity as O(2^m), which appears to omit the factor of m from the inner loop that iterates through all bit positions.

Learn more about how to find time and space complexity quickly.

Common Pitfalls

Pitfall 1: Misunderstanding the Relationship Between BFS Distance and Hamming Distance

The Problem: A common misconception is thinking that the BFS distance from a number directly gives us the Hamming distance. The code uses dist[x ^ ((1 << m) - 1)] to find the minimum BFS distance to the complement, then subtracts from m. This indirect approach can be confusing.

Why This Happens:

• BFS finds the minimum number of single-bit flips needed to reach any number from the array elements
• The complement of a number has maximum Hamming distance m from it
• If we can reach the complement in d steps, then the closest array element to the complement has Hamming distance m - d from our original number

Solution: Add clear documentation or consider a more direct approach:

# Direct approach: explicitly calculate Hamming distances
def maxHammingDistances(self, nums: List[int], m: int) -> List[int]:
    result = []
    for i, num1 in enumerate(nums):
        max_distance = 0
        for j, num2 in enumerate(nums):
            if i != j:
                # Direct Hamming distance calculation
                hamming_dist = bin(num1 ^ num2).count('1')
                max_distance = max(max_distance, hamming_dist)
        result.append(max_distance)
    return result

Pitfall 2: Incorrect Bit Mask for Complement Calculation

The Problem: Using the wrong expression for creating the all-ones mask. Common mistakes include:

• Using (1 << m) instead of (1 << m) - 1
• Using 2^m - 1 (which is XOR in Python, not exponentiation)

Why This Happens:

• (1 << m) gives us 100...0 (m zeros) which is 2^m
• (1 << m) - 1 gives us 111...1 (m ones) which is what we need for complement
• Python uses ** for exponentiation, not ^ (which is XOR)

Solution: Always verify the mask creation:

# Correct mask generation
all_bits_mask = (1 << m) - 1  # Creates m ones: 111...1

# Verify with example: m = 3
# (1 << 3) = 8 = 1000 in binary
# (1 << 3) - 1 = 7 = 0111 in binary ✓

# Wrong approaches to avoid:
# mask = 1 << m        # This gives 1000, not 0111
# mask = 2^m - 1       # This is XOR, not exponentiation

Pitfall 3: Handling Edge Cases with Array Size

The Problem: The algorithm assumes there are at least 2 elements in the array (since we need to compare with "any other element"). If the array has only 1 element, the problem becomes undefined.

Why This Happens:

• The problem statement says to find maximum Hamming distance to "any other element"
• With only one element, there is no "other element" to compare with

Solution: Add validation for edge cases:

def maxHammingDistances(self, nums: List[int], m: int) -> List[int]:
    # Handle edge case
    if len(nums) == 1:
        return [0]  # or raise an exception depending on requirements
  
    # Continue with the BFS approach...
    distances = [-1] * (1 << m)
    # ... rest of the implementation

Pitfall 4: Memory Issues with Large m Values

The Problem: The algorithm creates an array of size 2^m. For large values of m (e.g., m = 30), this requires enormous memory (over 1 billion integers).

Why This Happens:

• The BFS approach explores all possible m-bit numbers
• Storage requirement grows exponentially with m

Solution: For large m values, use the direct O(n²) approach instead:

def maxHammingDistances(self, nums: List[int], m: int) -> List[int]:
    # If m is too large, use direct calculation
    if m > 20:  # Threshold can be adjusted
        result = []
        for i in range(len(nums)):
            max_dist = 0
            for j in range(len(nums)):
                if i != j:
                    max_dist = max(max_dist, bin(nums[i] ^ nums[j]).count('1'))
            result.append(max_dist)
        return result
  
    # Otherwise use the BFS approach for better performance with small m
    # ... BFS implementation