### nik09877's blog

By nik09877, history, 5 months ago, 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 XOR nums2) + (nums1 XOR nums2) + ... + (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[(1 << 21)];
class Solution
{
public:
int solve(int i, int mask, int &n, vector<int> &a, vector<int> &b)
{
if (i == n)
return 0;

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));
}

}
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);
}
}; Comments (12)
 » Use Hungarian algorithm
•  » » Thnx! I will look that up ,but can you please tell why my dp + bitmask solution is not working?
•  » » Hungarian Algorithm is an overkill tbh. DP + bitset is way easier.
 » Auto comment: topic has been updated by nik09877 (previous revision, new revision, compare).
 » answer = min(answer, (a[i] ^ b[j]) + solve(i + 1, (mask ^ (1 << j)), n, a, b));
•  » » Thnx for pointing out the mistake.
 » 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[1<<14]. Hope it helps.
•  » » Oh man I was so close to solving it . Thnx for the help.
•  » » Thanks, first time solving the bitmask question and got stuck I know this but didn't notice.
 » 5 months ago, # | ← Rev. 2 →   This isn't related to your question but you can do this in 1D dp as well Spoilerint minimumXORSum(vector& a, vector& b) { int n = a.size(); vector dp(1<
 » There exists a polynomial solution to this problem too in $O(N^4)$. You can check it in HealthyUG '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.