Code Implementation

from functools import lru_cache

class Solution:
    def minimumXORSum(self, nums1, nums2):
        n = len(nums1)
        
        @lru_cache(None)
        def dp(i, mask):
            if i == n:
                return 0
            res = float('inf')
            for j in range(n):
                if not (mask & (1 << j)):
                    res = min(res, (nums1[i] ^ nums2[j]) + dp(i+1, mask | (1 << j)))
            return res
        return dp(0, 0)
      

#include <vector>
#include <climits>
using namespace std;

class Solution {
public:
    int minimumXORSum(vector<int>& nums1, vector<int>& nums2) {
        int n = nums1.size();
        int size = 1 << n;
        vector<int> dp(size, INT_MAX);
        dp[0] = 0;
        for (int mask = 0; mask < size; ++mask) {
            int i = __builtin_popcount(mask);
            if (i >= n) continue;
            for (int j = 0; j < n; ++j) {
                if (!(mask & (1 << j))) {
                    int next_mask = mask | (1 << j);
                    dp[next_mask] = min(dp[next_mask], dp[mask] + (nums1[i] ^ nums2[j]));
                }
            }
        }
        return dp[size - 1];
    }
};
      

import java.util.*;

class Solution {
    public int minimumXORSum(int[] nums1, int[] nums2) {
        int n = nums1.length;
        int size = 1 << n;
        int[] dp = new int[size];
        Arrays.fill(dp, Integer.MAX_VALUE);
        dp[0] = 0;
        for (int mask = 0; mask < size; ++mask) {
            int i = Integer.bitCount(mask);
            if (i >= n) continue;
            for (int j = 0; j < n; ++j) {
                if ((mask & (1 << j)) == 0) {
                    int nextMask = mask | (1 << j);
                    dp[nextMask] = Math.min(dp[nextMask], dp[mask] + (nums1[i] ^ nums2[j]));
                }
            }
        }
        return dp[size - 1];
    }
}
      

var minimumXORSum = function(nums1, nums2) {
    const n = nums1.length;
    const size = 1 << n;
    const dp = new Array(size).fill(Infinity);
    dp[0] = 0;
    for (let mask = 0; mask < size; ++mask) {
        let i = 0;
        for (let temp = mask; temp > 0; temp >>= 1) {
            if (temp & 1) i++;
        }
        if (i >= n) continue;
        for (let j = 0; j < n; ++j) {
            if ((mask & (1 << j)) === 0) {
                let nextMask = mask | (1 << j);
                dp[nextMask] = Math.min(dp[nextMask], dp[mask] + (nums1[i] ^ nums2[j]));
            }
        }
    }
    return dp[size - 1];
};
      

Problem Description

Given two arrays of integers nums1 and nums2, both of length n, you are to pair each element in nums1 with a unique element in nums2 (i.e., form a one-to-one mapping between the two arrays). For each pair, compute the bitwise XOR of the two numbers. Your task is to find the assignment that minimizes the total sum of these XOR values.

• Each element in nums1 must be paired with exactly one element in nums2, and vice versa.
• No element can be reused in a pairing.
• There is always at least one valid solution.

The goal is to return the minimum possible sum of XORs for any valid pairing.

Thought Process

At first glance, this problem appears similar to an assignment or matching problem, where we need to pair elements optimally. The brute-force way would be to try every possible permutation of nums2 and compute the XOR sum for each, keeping the minimum. However, this approach quickly becomes infeasible as n grows, since there are n! possible pairings.

To optimize, we need an efficient way to avoid redundant computations. Noticing that each step's choice only depends on which elements have already been used, we can use dynamic programming (DP) with bitmasking to represent the set of already-paired elements in nums2. This allows us to systematically build up solutions for smaller subproblems and reuse them, greatly reducing the number of computations.

Solution Approach

The optimized solution uses dynamic programming with bitmasking. Here’s how the approach works step by step:

1. State Representation:
   • Let i be the index in nums1 we are currently pairing.
   • Let mask be a bitmask integer where the j-th bit is 1 if nums2[j] has already been used in a pairing, and 0 otherwise.
2. Recursive Relation:
   • For each unused element nums2[j] (where bit j in mask is 0), try pairing nums1[i] with nums2[j].
   • Recursively solve for the next index (i+1) and the updated mask (mask | (1 << j)).
   • The cost of this step is (nums1[i] ^ nums2[j]) plus the minimum cost of the remaining pairings.
3. Memoization:
   • Store computed results for each (i, mask) to avoid redundant work.
4. Base Case:
   • If all elements have been paired (i == n), return 0.
5. Iterative Version:
   • Alternatively, use a DP array where dp[mask] is the minimum XOR sum for the used elements represented by mask.
   • Iterate through all possible masks and update accordingly.

The DP with bitmasking ensures that each possible assignment is considered exactly once, and overlapping subproblems are efficiently reused.

Example Walkthrough

Consider nums1 = [1, 2] and nums2 = [2, 3].

• Step 1: Start with i=0 (first element in nums1), mask=00 (no elements in nums2 used).
• Option A: Pair 1 with 2 (j=0), XOR is 1^2=3. Mark mask=01 (first element used).
  • Now i=1, mask=01. Pair 2 with 3 (j=1), XOR is 2^3=1, total sum is 3+1=4.
• Option B: Pair 1 with 3 (j=1), XOR is 1^3=2. Mark mask=10 (second element used).
  • Now i=1, mask=10. Pair 2 with 2 (j=0), XOR is 2^2=0, total sum is 2+0=2.
• The minimum XOR sum is 2 (from Option B).

The DP approach efficiently explores both options and remembers subproblem results for quick lookup.

Time and Space Complexity

• Brute-Force Approach:
  • Tries all n! permutations of nums2.
  • Time complexity: O(n!).
  • Space complexity: O(n) for recursion stack.
• DP with Bitmasking:
  • There are n positions and 2^n possible masks.
  • Each mask can be reached in up to n ways, so time complexity is O(n * 2^n).
  • Space complexity: O(2^n) for the DP/memoization table.

The DP approach is efficient for n <= 14 (as in the problem's constraints).

Summary

The Minimum XOR Sum of Two Arrays problem is a classic assignment problem that can be solved optimally using dynamic programming with bitmasking. By encoding the set of used elements in a bitmask and memoizing subproblems, we avoid redundant work and efficiently find the minimum sum. This approach leverages the structure of the problem—pairing elements uniquely—to achieve a solution that is both elegant and practical for the given constraints.