Minimum XOR Sum of Two Arrays — Bitmask DP

Problem

Assign each nums1[i] to exactly one nums2[j] (bijection). Minimize the total XOR sum.

Approach — Bitmask DP

dp[mask] = min XOR sum when mask indicates which nums2 elements are already assigned. Pop count of mask = how many nums1 elements processed.

Time: O(2^n * n) | Space: O(2^n)

Solutions

Python

class Solution:
    def minimumXORSum(self, nums1: list[int], nums2: list[int]) -> int:
        n=len(nums1)
        dp=[float('inf')]*(1<<n); dp[0]=0
        for mask in range(1<<n):
            i=bin(mask).count('1')  # next index in nums1
            if i>=n: continue
            for j in range(n):
                if not(mask&(1<<j)):
                    nm=mask|(1<<j)
                    dp[nm]=min(dp[nm],dp[mask]+(nums1[i]^nums2[j]))
        return dp[(1<<n)-1]

Complexity

Time: O(2^n * n) | Space: O(2^n)