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

c++

class Solution {
    int dp[1<<15];
    int helper(vector<int>& nums1, vector<int>& nums2, int mask, int index) {
        if(index == nums1.size()) return 0;
        if(dp[mask] != -1) return dp[mask];
        int& res = dp[mask] = INT_MAX;
        for(int i = 0; i < nums2.size(); i++) {
            if(mask & (1<<i)) continue;
            res = min(res, (nums1[index] ^ nums2[i]) + helper(nums1,nums2,mask | (1<<i), index + 1));
        }
        return res;
    }
public:
    int minimumXORSum(vector<int>& nums1, vector<int>& nums2) {
       memset(dp,-1,sizeof(dp));
        return helper(nums1,nums2,0,0);
    }
};