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] <= 10^7
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);
}
};
Use Hungarian algorithm
answer = min(answer, (a[i] ^ b[j]) + solve(i + 1, (mask ^ (1 << j)), n, a, b));
answer = min(answer, a[i] ^ b[j] + solve(i + 1, (mask ^ (1 << j)), n, a, b));
Plus operator has higher priority than xor so correct statement should be answer = min(answer, (a[i] ^ b[j]) + solve(i + 1, (mask ^ (1 << j)), n, a, b)); Second thing is dp size should be maximum dp[14][1<<14]. Hope it helps.
There exists a polynomial solution to this problem too in $$$O(N^4)$$$. You can check it in demoralizer 's youtube channel, he has discussed it pretty well.
No need to watch my video for that. The solution is just... weighted bipartite matching... There will be N² edges in total... So if you use Hungarian Algo, it's $$$O(N^4)$$$
But this is not required, DP+Bitmask is more than enough for this problem.