1879. Minimum XOR Sum of Two Arrays

Difficulty:
Related Topics:
Similar Questions:

Problem

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

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:

Solution

/**
 * @param {number[]} nums1
 * @param {number[]} nums2
 * @return {number}
 */
var minimumXORSum = function(nums1, nums2) {
    return helper(nums1, nums2, 0, 0, {});
};

var helper = function(nums1, nums2, i, bitmask, dp) {
    if (i === nums1.length) return 0;
    var key = `${i}-${bitmask}`;
    if (dp[key] !== undefined) return dp[key];
    var min = Number.MAX_SAFE_INTEGER;
    for (var j = 0; j < nums2.length; j++) {
        var mask = 1 << j;
        if (bitmask & mask) continue;
        min = Math.min(min, (nums1[i] ^ nums2[j]) + helper(nums1, nums2, i + 1, bitmask | mask, dp));
    }
    dp[key] = min;
    return min;
};

Explain:

nope.

Complexity: