nik09877's blog

By nik09877, history, 5 months ago, In English

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);
    }
};
 
 
 
 
  • Vote: I like it
  • +1
  • Vote: I do not like it

»
5 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Use Hungarian algorithm

  • »
    »
    5 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Thnx! I will look that up ,but can you please tell why my dp + bitmask solution is not working?

  • »
    »
    5 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Hungarian Algorithm is an overkill tbh. DP + bitset is way easier.

»
5 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by nik09877 (previous revision, new revision, compare).

»
5 months ago, # |
  Vote: I like it +5 Vote: I do not like it

answer = min(answer, (a[i] ^ b[j]) + solve(i + 1, (mask ^ (1 << j)), n, a, b));

»
5 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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.

  • »
    »
    5 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Oh man I was so close to solving it . Thnx for the help.

  • »
    »
    5 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Thanks, first time solving the bitmask question and got stuck I know this but didn't notice.

»
5 months ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

This isn't related to your question but you can do this in 1D dp as well

Spoiler

Usually, you use 2D DP in bitmask where the sequence of selection is important (like in TSP)

»
5 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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.

  • »
    »
    5 months ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    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.