Skip to content

1879. Minimum XOR Sum of Two Arrays 👍

  • Time: $O(2^n)$
  • Space: $O(1)$
 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 minimumXORSum(vector<int>& nums1, vector<int>& nums2) {
    return dfs(nums1, nums2, vector<int>(1 << nums2.size(), INT_MAX), 0, 0);
  }

 private:
  int dfs(const vector<int>& A, const vector<int>& B, vector<int>&& dp, int i,
          int mask) {
    if (i == A.size())
      return 0;
    if (dp[mask] < INT_MAX)
      return dp[mask];

    for (int j = 0; j < B.size(); ++j)
      if (!(mask >> j & 1))
        dp[mask] = min(dp[mask], (A[i] ^ B[j]) +
                                     dfs(A, B, move(dp), i + 1, mask | 1 << j));

    return dp[mask];
  }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
  public int minimumXORSum(int[] nums1, int[] nums2) {
    int[] dp = new int[1 << nums2.length];
    Arrays.fill(dp, Integer.MAX_VALUE);
    return dfs(nums1, nums2, dp, 0, 0);
  }

  private int dfs(int[] A, int[] B, int[] dp, int i, int mask) {
    if (i == A.length)
      return 0;
    if (dp[mask] < Integer.MAX_VALUE)
      return dp[mask];

    for (int j = 0; j < B.length; ++j)
      if ((mask >> j & 1) == 0)
        dp[mask] = Math.min(dp[mask], (A[i] ^ B[j]) + dfs(A, B, dp, i + 1, mask | 1 << j));

    return dp[mask];
  }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
class Solution:
  def minimumXORSum(self, nums1: List[int], nums2: List[int]) -> int:
    @functools.lru_cache(None)
    def dp(mask: int) -> int:
      i = bin(mask).count("1")
      if i == len(nums1):
        return 0
      return min((nums1[i] ^ nums2[j]) + dp(mask | 1 << j)
                 for j in range(len(nums2)) if not mask >> j & 1)
    return dp(0)