Minimum XOR Sum of Two Arrays - Video Solutions

Problem Overview: You are given two arrays of equal length nums1 and nums2. The task is to pair every element in nums1 with exactly one element in nums2 such that the total XOR sum of all pairs is minimized. Since every element must be used exactly once, the challenge is effectively finding the minimum-cost permutation.

Approach 1: Dynamic Programming with Bitmasking (Time: O(n * 2^n), Space: O(2^n))

This approach models the problem as a state transition using dynamic programming combined with bitmasking. A bitmask represents which elements from nums2 are already used. For each mask, the number of set bits tells you how many elements from nums1 have already been paired. You iterate through all elements in nums2, and if the bit is not set in the mask, you try pairing that element with the current index in nums1. The transition becomes dp[newMask] = min(dp[newMask], dp[mask] + (nums1[i] ^ nums2[j])). The key insight is that the mask uniquely represents a pairing state, eliminating repeated work across permutations. This reduces a factorial search space to 2^n states, making it feasible for n ≤ 14. Bit operations efficiently track which elements are used.

Approach 2: Backtracking with Memoization (Time: O(n * 2^n), Space: O(2^n))

This approach performs recursive exploration of all pairings but caches intermediate results to avoid recomputation. At each recursion level, you pick the next index in nums1 and try pairing it with every unused element in nums2. A mask tracks which elements in nums2 are already selected. The recursive state is defined by the mask (or index plus mask). Memoization stores the minimum XOR cost for that state so future calls return instantly. The pruning effect of caching converts an otherwise factorial backtracking search into roughly n * 2^n states. The algorithm heavily relies on bit manipulation to check and update mask bits efficiently.

Recommended for interviews: The dynamic programming with bitmasking solution is what interviewers typically expect. It demonstrates that you recognize the permutation constraint and convert it into a DP state using bitmasks. Backtracking with memoization shows the same idea but arrives at it through recursive exploration. Starting with the backtracking intuition and then optimizing to DP with bitmasking is often the clearest way to communicate your reasoning during an interview.