3141. Maximum Hamming Distances 🔒

Description

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).

Example 1:

Input: nums = [9,12,9,11], m = 4

Output: [2,3,2,3]

Explanation:

The binary representation of nums = [1001,1100,1001,1011].

The maximum hamming distances for each index are:

nums[0]: 1001 and 1100 have a distance of 2.
nums[1]: 1100 and 1011 have a distance of 3.
nums[2]: 1001 and 1100 have a distance of 2.
nums[3]: 1011 and 1100 have a distance of 3.

Example 2:

Input: nums = [3,4,6,10], m = 4

Output: [3,3,2,3]

Explanation:

The binary representation of nums = [0011,0100,0110,1010].

The maximum hamming distances for each index are:

nums[0]: 0011 and 0100 have a distance of 3.
nums[1]: 0100 and 0011 have a distance of 3.
nums[2]: 0110 and 1010 have a distance of 2.
nums[3]: 1010 and 0100 have a distance of 3.

Constraints:

1 <= m <= 17
2 <= nums.length <= 2^m
0 <= nums[i] < 2^m

Solutions

Solution 1: Reverse Thinking + BFS

The problem requires us to find the maximum Hamming distance between each element and other elements in the array. We can think in reverse: for each element, we take its complement and find the minimum Hamming distance to other elements in the array. Then, the maximum Hamming distance we are looking for is $m$ minus this minimum Hamming distance.

We can use Breadth-First Search (BFS) to find the minimum Hamming distance from each complemented element to other elements.

The specific steps are as follows:

Initialize an array $\text{dist}$ with a length of $2^m$ to record the minimum Hamming distance from each complemented element to other elements. Initially, all are set to $-1$.
Traverse the array $\text{nums}$, set the complement of each element to $0$, and add it to the queue $\text{q}$.
Starting from $k = 1$, continuously traverse the queue $\text{q}$. Each time, take out the elements in the queue, perform $m$ complement operations on them, add the complemented elements to the queue $\text{t}$, and set the minimum Hamming distance to the original element to $k$.
Repeat step 3 until the queue is empty.

Finally, we traverse the array $\text{nums}$, take the complement of each element as the index, and take out the corresponding minimum Hamming distance from the $\text{dist}$ array. Then, $m$ minus this value is the maximum Hamming distance we are looking for.

The time complexity is $O(2^m)$, and the space complexity is $O(2^m)$, where $m$ is the integer given in the problem.

Python3JavaC++GoTypeScript

class Solution:
    def maxHammingDistances(self, nums: List[int], m: int) -> List[int]:
        dist = [-1] * (1 << m)
        for x in nums:
            dist[x] = 0
        q = nums
        k = 1
        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
        return [m - dist[x ^ ((1 << m) - 1)] for x in nums]

class Solution {
    public int[] maxHammingDistances(int[] nums, int m) {
        int[] dist = new int[1 << m];
        Arrays.fill(dist, -1);
        Deque<Integer> q = new ArrayDeque<>();
        for (int x : nums) {
            dist[x] = 0;
            q.offer(x);
        }
        for (int k = 1; !q.isEmpty(); ++k) {
            for (int t = q.size(); t > 0; --t) {
                int x = q.poll();
                for (int i = 0; i < m; ++i) {
                    int y = x ^ (1 << i);
                    if (dist[y] == -1) {
                        q.offer(y);
                        dist[y] = k;
                    }
                }
            }
        }
        for (int i = 0; i < nums.length; ++i) {
            nums[i] = m - dist[nums[i] ^ ((1 << m) - 1)];
        }
        return nums;
    }
}

class Solution {
public:
    vector<int> maxHammingDistances(vector<int>& nums, int m) {
        int dist[1 << m];
        memset(dist, -1, sizeof(dist));
        queue<int> q;
        for (int x : nums) {
            dist[x] = 0;
            q.push(x);
        }
        for (int k = 1; q.size(); ++k) {
            for (int t = q.size(); t; --t) {
                int x = q.front();
                q.pop();
                for (int i = 0; i < m; ++i) {
                    int y = x ^ (1 << i);
                    if (dist[y] == -1) {
                        dist[y] = k;
                        q.push(y);
                    }
                }
            }
        }
        for (int& x : nums) {
            x = m - dist[x ^ ((1 << m) - 1)];
        }
        return nums;
    }
};

func maxHammingDistances(nums []int, m int) []int {
    dist := make([]int, 1<<m)
    for i := range dist {
        dist[i] = -1
    }
    q := []int{}
    for _, x := range nums {
        dist[x] = 0
        q = append(q, x)
    }
    for k := 1; len(q) > 0; k++ {
        t := []int{}
        for _, x := range q {
            for i := 0; i < m; i++ {
                y := x ^ (1 << i)
                if dist[y] == -1 {
                    dist[y] = k
                    t = append(t, y)
                }
            }
        }
        q = t
    }
    for i, x := range nums {
        nums[i] = m - dist[x^(1<<m-1)]
    }
    return nums
}

function maxHammingDistances(nums: number[], m: number): number[] {
    const dist: number[] = Array.from({ length: 1 << m }, () => -1);
    const q: number[] = [];
    for (const x of nums) {
        dist[x] = 0;
        q.push(x);
    }
    for (let k = 1; q.length; ++k) {
        const t: number[] = [];
        for (const x of q) {
            for (let i = 0; i < m; ++i) {
                const y = x ^ (1 << i);
                if (dist[y] === -1) {
                    dist[y] = k;
                    t.push(y);
                }
            }
        }
        q.splice(0, q.length, ...t);
    }
    for (let i = 0; i < nums.length; ++i) {
        nums[i] = m - dist[nums[i] ^ ((1 << m) - 1)];
    }
    return nums;
}

3141. Maximum Hamming Distances 🔒

Description

Solutions

Solution 1: Reverse Thinking + BFS

Comments