1879. Minimum XOR Sum of Two Arrays LeetCode Solution

In this guide, you will get 1879. Minimum XOR Sum of Two Arrays LeetCode Solution with the best time and space complexity. The solution to Minimum XOR Sum of Two Arrays problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.

Problem Statement
Complexity Analysis
Minimum XOR Sum of Two Arrays solution in C++
Minimum XOR Sum of Two Arrays solution in Java
Minimum XOR Sum of Two Arrays solution in Python
Additional Resources

1879. Minimum XOR Sum of Two Arrays LeetCode Solution image

Problem Statement of Minimum XOR Sum of Two Arrays

You are given two integer arrays nums1 and nums2 of length n.
The XOR sum of the two integer arrays is (nums1[0] XOR nums2[0]) + (nums1[1] XOR nums2[1]) + … + (nums1[n – 1] XOR nums2[n – 1]) (0-indexed).

For example, the XOR sum of [1,2,3] and [3,2,1] is equal to (1 XOR 3) + (2 XOR 2) + (3 XOR 1) = 2 + 0 + 2 = 4.

Rearrange the elements of nums2 such that the resulting XOR sum is minimized.
Return the XOR sum after the rearrangement.

Example 1:

Input: nums1 = [1,2], nums2 = [2,3]
Output: 2
Explanation: Rearrange nums2 so that it becomes [3,2].
The XOR sum is (1 XOR 3) + (2 XOR 2) = 2 + 0 = 2.
Example 2:

Input: nums1 = [1,0,3], nums2 = [5,3,4]
Output: 8
Explanation: Rearrange nums2 so that it becomes [5,4,3].
The XOR sum is (1 XOR 5) + (0 XOR 4) + (3 XOR 3) = 4 + 4 + 0 = 8.

Constraints:

n == nums1.length
n == nums2.length
1 <= n <= 14
0 <= nums1[i], nums2[i] <= 107

Complexity Analysis

Time Complexity: O(2^n)
Space Complexity: O(1)

1879. Minimum XOR Sum of Two Arrays LeetCode Solution in C++

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];
  }
};
/* code provided by PROGIEZ */

1879. Minimum XOR Sum of Two Arrays LeetCode Solution in Java

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];
  }
}
// code provided by PROGIEZ

1879. Minimum XOR Sum of Two Arrays LeetCode Solution in Python

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)
 # code by PROGIEZ