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 \(\textit{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 \(\textit{nums}\), set the complement of each element to \(0\), and add it to the queue \(\textit{q}\).
Starting from \(k = 1\), continuously traverse the queue \(\textit{q}\). Each time, take out the elements in the queue, perform \(m\) complement operations on them, add the complemented elements to the queue \(\textit{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 \(\textit{nums}\), take the complement of each element as the index, and take out the corresponding minimum Hamming distance from the \(\textit{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