Description

Submission

class Solution {
public:
    int minimumXORSum(vector<int>& nums1, vector<int>& nums2) {
        int n = nums1.size();
        vector<int> dp(1<<n, INT_MAX/2);
        vector<int> dp2;
        dp[0] = 0;

        // pair the first-i elements in nums1 with arbitrary numbers in nums2
        for(int i = 0; i < n; ++i) {
            dp2 = dp;
            for(int state = 0; state < (1<<n); ++state) {
                dp[state] = INT_MAX / 2;
                for(int j = 0; j < n; ++j) {
                    if((state>>j)&1) dp[state] = min(dp2[state-(1<<j)] + (nums1[i]^nums2[j]), dp[state]);
                }
            }
        }

        return dp[(1<<n)-1];
    }
};

class Solution {
public:
    int minimumXORSum(vector<int>& nums1, vector<int>& nums2) {
        int n = nums1.size();
        
        vector<int> dp(1<<n, INT_MAX);
        vector<int> dp2;
        dp[0] = 0;

        for(int i = 0; i < n; ++i) {
            dp2 = dp;
            for(int state = 0; state < (1 << n); ++state) {
                if(__builtin_popcount(state) == i + 1) {
                    for(int j = 0; j < n; ++j) {
                        if((state>>j)&1) 
                            dp[state] = min(dp[state], dp[state-(1<<j)] + (nums1[i] ^ nums2[j]));
                    }
                }
            }
        }

        return dp[(1<<n)-1];
    }
};