You are given two integer arrays nums1 and nums2 of length n.
The XOR sum of the two integer arrays is (nums1[0] XOR nums2[0]) + (nums1[1] XOR nums2[1]) + ... + (nums1[n - 1] XOR nums2[n - 1]) (0-indexed).
[1,2,3] and [3,2,1] is equal to (1 XOR 3) + (2 XOR 2) + (3 XOR 1) = 2 + 0 + 2 = 4.Rearrange the elements of nums2 such that the resulting XOR sum is minimized.
Return the XOR sum after the rearrangement.
Example 1:
Input: nums1 = [1,2], nums2 = [2,3] Output: 2 Explanation: Rearrangenums2so that it becomes[3,2]. The XOR sum is (1 XOR 3) + (2 XOR 2) = 2 + 0 = 2.
Example 2:
Input: nums1 = [1,0,3], nums2 = [5,3,4] Output: 8 Explanation: Rearrangenums2so that it becomes[5,4,3]. The XOR sum is (1 XOR 5) + (0 XOR 4) + (3 XOR 3) = 4 + 4 + 0 = 8.
Constraints:
n == nums1.lengthn == nums2.length1 <= n <= 140 <= nums1[i], nums2[i] <= 107Problem 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.
This approach uses dynamic programming combined with bitmasking to find the minimum XOR sum efficiently. Here, the state of the DP is represented as dp[mask], where mask is a bitmask that tells us which numbers in nums2 have been used. The i-th bit of mask is 1 if the i-th number is used, otherwise it's 0. We initialize dp[0] to 0 because the XOR sum for empty selections is 0. Then, for each dp[mask], we iterate over all unused numbers in nums2 (those with the 0 bit in mask) and update the dp table.
The code uses a DP array of size 2^n to record the minimum XOR sum possible with various combinations of used elements in nums2. We use bitmasking to represent the selection of elements. We iterate over possible selections of nums2 elements (denoted by the bitmask) and update the DP table accordingly.
The time complexity is O(n * 2^n) because there are 2^n states and we process each state in O(n) time. The space complexity is O(2^n) for storing the DP table.
This approach utilizes backtracking to generate permutations of the nums2 list, computing the XOR sum for each permutation. To optimize, memoization is employed to cache results of already computed subproblems, preventing redundant calculations. This effectively reduces the combinatorial explosion when similar subproblems are encountered.
This C solution uses recursive backtracking with memoization. The function solve takes the current index in nums1, a bitmask representing used elements in nums2, and recursively explores all options with memoization to avoid recomputation.
The time complexity is potentially O(n^2 * 2^n) when recalling n recursive calls for 2^n masks. The space complexity is O(n * 2^n) due to the use of the memoization table.
Python
Java
C++
Go
TypeScript
| Approach | Complexity |
|---|---|
| Approach 1: Dynamic Programming with Bitmasking | The time complexity is |
| Approach 2: Backtracking with Memoization | The time complexity is potentially |
| Default Approach | — |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Dynamic Programming with Bitmasking | O(n * 2^n) | O(2^n) | Best general solution when n ≤ 14 and all pairings must be evaluated efficiently |
| Backtracking with Memoization | O(n * 2^n) | O(2^n) | Good for understanding the permutation search first, then optimizing using memoization |
Leetcode 5756. Minimum XOR Sum of Two Arrays • Fraz • 3,637 views views
Watch 9 more video solutions →Practice Minimum XOR Sum of Two Arrays with our built-in code editor and test cases.
Practice on FleetCode