Problem

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

Examples

Example 1:

1
2
3
4
5
6
7
8
9

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:

1
2
3
4
5
6
7
8
9

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

Solution

Method 1 – Bit Manipulation and Counting

Intuition

The Hamming distance between two numbers is the number of differing bits. For each number, to maximize the Hamming distance, we want to find another number in the array that differs from it in as many bit positions as possible. For each bit position, count how many numbers have a 0 or 1, and for each number, the maximum Hamming distance is the sum of positions where the majority of numbers differ from its bit.

Approach

  1. For each bit position (from 0 to m-1), count how many numbers have a 0 and how many have a 1 at that position.
  2. For each number, for each bit position, if its bit is 0, the maximum Hamming distance at that bit is the number of numbers with 1 at that position, and vice versa.
  3. For each number, sum the maximum possible differing bits across all positions to get the answer for that number.
  4. Return the answer array.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

class Solution {
public:
    vector<int> maximumHammingDistances(vector<int>& nums, int m) {
        int n = nums.size();
        vector<int> cnt0(m), cnt1(m);
        for (int x : nums) {
            for (int i = 0; i < m; ++i) {
                if ((x >> i) & 1) cnt1[i]++;
                else cnt0[i]++;
            }
        }
        vector<int> ans(n);
        for (int i = 0; i < n; ++i) {
            int res = 0;
            for (int j = 0; j < m; ++j) {
                if ((nums[i] >> j) & 1) res += cnt0[j];
                else res += cnt1[j];
            }
            ans[i] = res;
        }
        return ans;
    }
};
 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

func maximumHammingDistances(nums []int, m int) []int {
    n := len(nums)
    cnt0 := make([]int, m)
    cnt1 := make([]int, m)
    for _, x := range nums {
        for i := 0; i < m; i++ {
            if (x>>i)&1 == 1 {
                cnt1[i]++
            } else {
                cnt0[i]++
            }
        }
    }
    ans := make([]int, n)
    for i, x := range nums {
        res := 0
        for j := 0; j < m; j++ {
            if (x>>j)&1 == 1 {
                res += cnt0[j]
            } else {
                res += cnt1[j]
            }
        }
        ans[i] = res
    }
    return ans
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22

class Solution {
    public int[] maximumHammingDistances(int[] nums, int m) {
        int n = nums.length;
        int[] cnt0 = new int[m], cnt1 = new int[m];
        for (int x : nums) {
            for (int i = 0; i < m; ++i) {
                if (((x >> i) & 1) == 1) cnt1[i]++;
                else cnt0[i]++;
            }
        }
        int[] ans = new int[n];
        for (int i = 0; i < n; ++i) {
            int res = 0;
            for (int j = 0; j < m; ++j) {
                if (((nums[i] >> j) & 1) == 1) res += cnt0[j];
                else res += cnt1[j];
            }
            ans[i] = res;
        }
        return ans;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21

class Solution {
    fun maximumHammingDistances(nums: IntArray, m: Int): IntArray {
        val n = nums.size
        val cnt0 = IntArray(m)
        val cnt1 = IntArray(m)
        for (x in nums) {
            for (i in 0 until m) {
                if ((x shr i) and 1 == 1) cnt1[i]++ else cnt0[i]++
            }
        }
        val ans = IntArray(n)
        for (i in 0 until n) {
            var res = 0
            for (j in 0 until m) {
                if ((nums[i] shr j) and 1 == 1) res += cnt0[j] else res += cnt1[j]
            }
            ans[i] = res
        }
        return ans
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21

class Solution:
    def maximumHammingDistances(self, nums: list[int], m: int) -> list[int]:
        n = len(nums)
        cnt0 = [0] * m
        cnt1 = [0] * m
        for x in nums:
            for i in range(m):
                if (x >> i) & 1:
                    cnt1[i] += 1
                else:
                    cnt0[i] += 1
        ans = []
        for x in nums:
            res = 0
            for i in range(m):
                if (x >> i) & 1:
                    res += cnt0[i]
                else:
                    res += cnt1[i]
            ans.append(res)
        return ans
 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
30

impl Solution {
    pub fn maximum_hamming_distances(nums: Vec<i32>, m: i32) -> Vec<i32> {
        let n = nums.len();
        let m = m as usize;
        let mut cnt0 = vec![0; m];
        let mut cnt1 = vec![0; m];
        for &x in &nums {
            for i in 0..m {
                if (x >> i) & 1 == 1 {
                    cnt1[i] += 1;
                } else {
                    cnt0[i] += 1;
                }
            }
        }
        let mut ans = vec![0; n];
        for (i, &x) in nums.iter().enumerate() {
            let mut res = 0;
            for j in 0..m {
                if (x >> j) & 1 == 1 {
                    res += cnt0[j];
                } else {
                    res += cnt1[j];
                }
            }
            ans[i] = res;
        }
        ans
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22

class Solution {
    maximumHammingDistances(nums: number[], m: number): number[] {
        const n = nums.length;
        const cnt0 = Array(m).fill(0), cnt1 = Array(m).fill(0);
        for (const x of nums) {
            for (let i = 0; i < m; ++i) {
                if ((x >> i) & 1) cnt1[i]++;
                else cnt0[i]++;
            }
        }
        const ans = [];
        for (const x of nums) {
            let res = 0;
            for (let i = 0; i < m; ++i) {
                if ((x >> i) & 1) res += cnt0[i];
                else res += cnt1[i];
            }
            ans.push(res);
        }
        return ans;
    }
}

Complexity

  • ⏰ Time complexity: O(n * m), since we process each bit of each number twice.
  • 🧺 Space complexity: O(m), for the bit counters.