3141. Maximum Hamming Distances π
Description
Given an array nums
and an integer m
, with each element nums[i]
satisfying 0 <= nums[i] < 2m
, 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 <= 2m
0 <= nums[i] < 2m
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.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 |
|