Skip to main content
Talentd

Minimum XOR Sum of Two Arrays - Solution & Explanation

HardArrayDynamic ProgrammingBit ManipulationBitmask17 min readAsked at: Medianet
Practice this problem

Problem Statement

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).

  • For example, the XOR sum of [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: Rearrange nums2 so 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: Rearrange nums2 so 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.length
  • n == nums2.length
  • 1 <= n <= 14
  • 0 <= nums1[i], nums2[i] <= 107

Approach Overview

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.

Approach 1: Approach 1: Dynamic Programming with Bitmasking

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.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

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.

Try this approach in the editor ā†’

Approach 2: Approach 2: Backtracking with Memoization

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.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

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.

Try this approach in the editor ā†’

Approach 3: Default Approach

Code

PythonJavaC++GoTypeScript

Python

Java

C++

Go

TypeScript

Try this approach in the editor ā†’

Complexity Comparison

ApproachComplexity
Approach 1: Dynamic Programming with Bitmasking

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.

Approach 2: Backtracking with Memoization

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.

Default Approachā€”

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Dynamic Programming with BitmaskingO(n * 2^n)O(2^n)Best general solution when n ā‰¤ 14 and all pairings must be evaluated efficiently
Backtracking with MemoizationO(n * 2^n)O(2^n)Good for understanding the permutation search first, then optimizing using memoization

Video Solution

Leetcode 5756. Minimum XOR Sum of Two Arrays ā€¢ Fraz ā€¢ 3,675 views views

Watch 8 more video solutions ā†’

Frequently Asked Questions

Is Minimum XOR Sum of Two Arrays easy or hard?
Minimum XOR Sum of Two Arrays is classified as a Hard problem. The challenge comes from recognizing that the pairing constraint forms a permutation problem and solving it efficiently using bitmask dynamic programming.
Minimum XOR Sum of Two Arrays Python/Java solution
Python and Java implementations typically use DP with a bitmask integer representing used elements of nums2. The algorithm iterates through all masks, counts set bits to determine the index in nums1, and updates the DP state with the XOR cost. The same logic works across Python, Java, C++, and JavaScript.
How to solve Minimum XOR Sum of Two Arrays in O(n)?
An O(n) solution is not possible because the problem requires evaluating pairings between two arrays, which is essentially a permutation optimization problem. The best known approach uses dynamic programming with bitmasking and runs in O(n * 2^n) time.
What is the best approach for Minimum XOR Sum of Two Arrays?
Dynamic programming with bitmasking is the most efficient approach. Each bitmask represents which elements from nums2 are already paired, and DP stores the minimum XOR cost for that state. This reduces the permutation search from O(n!) to O(n * 2^n), which is manageable for n up to about 14.
Is Minimum XOR Sum of Two Arrays asked at Google/Amazon/Meta?
This type of problem appears in interviews at companies like Google, Amazon, and Meta because it tests bitmask dynamic programming and permutation optimization. Variations of assignment problems and XOR minimization are common in advanced algorithm rounds.
What data structure is used in Minimum XOR Sum of Two Arrays?
The core technique uses a bitmask integer to represent which elements of nums2 are already used. A dynamic programming array or hash map stores the minimum XOR sum for each mask state. Efficient bit manipulation operations check and update the mask during transitions.
What is the time complexity of Minimum XOR Sum of Two Arrays?
The optimal solution runs in O(n * 2^n) time. There are 2^n possible masks representing used elements of nums2, and for each state you try up to n pairings. Space complexity is O(2^n) for the DP table or memoization cache.

Ready to solve this problem?

Practice Minimum XOR Sum of Two Arrays with our built-in code editor and test cases.

Practice on FleetCode
Previous

Choose Numbers From Two Arrays in Range

Next

Fair Distribution of Cookies