[Help] Minimum XOR Sum of Two Arrays.

Revision en1, by nik09877, 2021-05-29 20:26:26

Came In the Recent Leetcode Contest,Don't know where my code went wrong Link To The 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).

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

Constraints:

n == nums1.length
n == nums2.length
1 <= n <= 14
0 <= nums1[i], nums2[i] <= 107
int dp[21][(1 << 21)];
class Solution
{
public:
    int solve(int i, int mask, int &n, vector<int> &a, vector<int> &b)
    {
        if (i == n)
            return 0;

        if (dp[i][mask] != -1)
            return dp[i][mask];

        int answer = INT_MAX;
        for (int j = 0; j < n; j++)
        {
            if (mask & (1 << j))
                answer = min(answer, a[i] ^ b[j] + solve(i + 1, (mask ^ (1 << j)), n, a, b));
        }

        return dp[i][mask] = answer;
    }
    int minimumXORSum(vector<int> &a, vector<int> &b)
    {
        memset(dp, -1, sizeof dp);
        int n = a.size();
        return solve(0, (1 << n) - 1, n, a, b);
    }
};

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en2 English nik09877 2021-05-29 21:10:42 1 Tiny change: '2[i] <= 107\n~~~~~\n' -> '2[i] <= 10^7\n~~~~~\n'
en1 English nik09877 2021-05-29 20:26:26 1544 Initial revision (published)