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
23
24
25
class Solution {
 public:
  int minimumXORSum(vector<int>& nums1, vector<int>& nums2) {
    vector<int> mem(1 << nums2.size(), INT_MAX);
    return minimumXORSum(nums1, nums2, 0, mem);
  }

 private:
  int minimumXORSum(const vector<int>& nums1, const vector<int>& nums2,
                    unsigned mask, vector<int>& mem) {
    const int i = popcount(mask);
    if (i == nums1.size())
      return 0;
    if (mem[mask] < INT_MAX)
      return mem[mask];

    for (int j = 0; j < nums2.size(); ++j)
      if ((mask >> j & 1) == 0)
        mem[mask] =
            min(mem[mask], (nums1[i] ^ nums2[j]) +
                               minimumXORSum(nums1, nums2, mask | 1 << j, mem));

    return mem[mask];
  }
};

 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(int[] nums1, int[] nums2) {
    int[] mem = new int[1 << nums2.length];
    Arrays.fill(mem, Integer.MAX_VALUE);
    return minimumXORSum(nums1, nums2, 0, mem);
  }

  private int minimumXORSum(int[] nums1, int[] nums2, int mask, int[] mem) {
    final int i = Integer.bitCount(mask);
    if (i == nums1.length)
      return 0;
    if (mem[mask] < Integer.MAX_VALUE)
      return mem[mask];

    for (int j = 0; j < nums2.length; ++j)
      if ((mask >> j & 1) == 0)
        mem[mask] = Math.min(mem[mask], (nums1[i] ^ nums2[j]) +
                                            minimumXORSum(nums1, nums2, mask | 1 << j, mem));

    return mem[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 = mask.bit_count()
      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)