1879. Minimum XOR Sum of Two Arrays

Problem

Tags: Array, Dynamic Programming, Bit Manipulation, Bitmask

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.

Example 1:

Input: nums1 = [1,2], nums2 = [2,3]
Output: 2
Explanation: Rearrange nums2 so that it becomes [3,2].
The XOR sum is (1 XOR 3) + (2 XOR 2) = 2 + 0 = 2.

Example 2:

Input: nums1 = [1,0,3], nums2 = [5,3,4]
Output: 8
Explanation: Rearrange nums2 so that it becomes [5,4,3]. 
The XOR sum is (1 XOR 5) + (0 XOR 4) + (3 XOR 3) = 4 + 4 + 0 = 8.

Constraints:

• n == nums1.length
• n == nums2.length
• 1 <= n <= 14
• 0 <= nums1[i], nums2[i] <= 10^7

Code

CPP

// 1879. Minimum XOR Sum of Two Arrays (10/6/53378)
// Runtime: 12 ms (94.36%) Memory: 10.44 MB (52.82%) 

#include <bits/stdc++.h>
using namespace std;
namespace minimum_cost_maximum_flow {
template <class F = int, class C = int> struct minimum_cost_maximum_flow {
    struct edge {
        edge(int _v, F _c, C _w) : v(_v), c(_c), w(_w) {}
        int v;
        F c;
        C w;
    };
    minimum_cost_maximum_flow(int _n, int _src, int _snk,
                              F _all = numeric_limits<F>::max())
        : n(_n), src(_src), snk(_snk), bg(_n), vis(n), dis(n), all(_all),
          flow(0), cost(0) {}
    void add(int u, int v, F c, C w) {
        bg[u].push_back(int(eg.size()));
        eg.push_back(edge(v, c, w));
        bg[v].push_back(int(eg.size()));
        eg.push_back(edge(u, 0, -w));
    }
    int spfa() {
        vector<int> in(n, 0);
        queue<int> qu;
        fill(vis.begin(), vis.end(), 0);
        dis[src] = 0;
        vis[src] = in[src] = 1;
        qu.push(src);
        while (!qu.empty()) {
            int u = qu.front();
            qu.pop();
            in[u] = 0;
            for (int i = 0; i < int(bg[u].size()); ++i) {
                edge &e = eg[bg[u][i]];
                if (e.c != 0 && (!vis[e.v] || dis[u] + e.w < dis[e.v])) {
                    dis[e.v] = dis[u] + e.w;
                    vis[e.v] = 1;
                    if (!in[e.v]) {
                        in[e.v] = 1;
                        qu.push(e.v);
                    }
                }
            }
        }
        return vis[snk];
    }
    F dfs(int u, F f) {
        if (u == snk)
            return f;
        F g = f;
        vis[u] = 1;
        for (int i = 0; i < int(bg[u].size()); ++i) {
            edge &e = eg[bg[u][i]], &ev = eg[bg[u][i] ^ 1];
            if (e.c != 0 && dis[e.v] == dis[u] + e.w && !vis[e.v]) {
                F t = dfs(e.v, min(g, e.c));
                g -= t;
                e.c -= t;
                ev.c += t;
                cost += t * e.w;
                if (g == 0)
                    return f;
            }
        }
        return f - g;
    }
    pair<F, C> run() {
        while (all != 0 && spfa()) {
            F t;
            do {
                fill(vis.begin(), vis.end(), 0);
                flow += (t = dfs(src, all));
                all -= t;
            } while (t != 0);
        }
        return make_pair(flow, cost);
    }
    int n, src, snk;
    vector<vector<int>> bg;
    vector<edge> eg;
    vector<int> vis;
    vector<C> dis;
    F all, flow;
    C cost;
};
} // namespace minimum_cost_maximum_flow
class Solution {
public:
    int minimumXORSum(vector<int>& nums1, vector<int>& nums2) {
        int n=nums1.size();
        minimum_cost_maximum_flow::minimum_cost_maximum_flow f(2*n+2,2*n,2*n+1);
        for(int i=0;i<n;++i)f.add(2*n,i,1,0),f.add(n+i,2*n+1,1,0);
        for(int i=0;i<n;++i)for(int j=0;j<n;++j)f.add(i,n+j,1,(nums1[i]^nums2[j]));
        
        int xabc = 0;
        return f.run().second;
    }
};