LeetCode 1879. Minimum XOR Sum of Two Arrays

Posted on Edited on In 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
public:
    int minimumXORSum(vector<int>& nums1, vector<int>& nums2) {
        int n = nums1.size(), range = 1 << n;
        vector<int> dp(range, INT_MAX);
        dp[0] = 0;
        for (int mask = 1; mask < range; ++mask) {
            int bits = __builtin_popcount(mask);
            for (int pos = 0; pos < n; ++pos)
                if (mask >> pos & 1)
                    dp[mask] = min(dp[mask], dp[mask ^ (1 << pos)] + (nums1[bits - 1] ^ nums2[pos]));
        }
        return dp[range - 1];
    }
};