Skip to content

3141. Maximum Hamming Distances 👍

  • Time: $O(m \cdot 2^m)$
  • Space: $O(2^m)$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
 public:
  vector<int> maxHammingDistances(vector<int>& nums, int m) {
    const int maxMask = 1 << m;
    vector<int> ans;
    // dp[i] := the maximum hamming distance from i to any number in `nums`
    vector<int> dp(maxMask, INT_MIN);

    for (const int num : nums)
      dp[num] = 0;

    for (int bit = 0; bit < m; ++bit) {
      vector<int> newDp(maxMask);
      for (int mask = 0; mask < maxMask; ++mask)
        newDp[mask] = max(dp[mask], dp[mask ^ (1 << bit)] + 1);
      dp = std::move(newDp);
    }

    for (const int num : nums)
      ans.push_back(dp[num]);

    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
class Solution {
  public int[] maxHammingDistances(int[] nums, int m) {
    final int MAX_MASK = 1 << m;
    int[] ans = new int[nums.length];
    // dp[i] := the maximum hamming distance from i to any number in `nums`
    int[] dp = new int[MAX_MASK];
    Arrays.fill(dp, Integer.MIN_VALUE);

    for (final int num : nums)
      dp[num] = 0;

    for (int bit = 0; bit < m; ++bit) {
      int[] newDp = new int[MAX_MASK];
      for (int mask = 0; mask < MAX_MASK; ++mask)
        newDp[mask] = Math.max(dp[mask], dp[mask ^ (1 << bit)] + 1);
      dp = newDp;
    }

    for (int i = 0; i < nums.length; ++i)
      ans[i] = dp[nums[i]];

    return ans;
  }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
class Solution:
  def maxHammingDistances(self, nums: list[int], m: int) -> list[int]:
    MAX_MASK = 1 << m
    # dp[i] := the maximum hamming distance from i to any number in `nums`
    dp = [-math.inf] * MAX_MASK

    for num in nums:
      dp[num] = 0

    for bit in range(m):
      newDp = [0] * MAX_MASK
      for mask in range(MAX_MASK):
        newDp[mask] = max(dp[mask], dp[mask ^ (1 << bit)] + 1)
      dp = newDp

    return [dp[num] for num in nums]