Minimum XOR Sum of Two Arrays

June 5, 20265 min read

leetcodeproblemhardarraysdynamic-programmingbit-manipulation

LeetCode Minimum XOR Sum of Two Arrays (Problem 1879) asks: given two integer arrays nums1 and nums2 of equal length n, rearrange nums2 so that the XOR sum (nums1[0] XOR nums2[0]) + (nums1[1] XOR nums2[1]) + ... + (nums1[n-1] XOR nums2[n-1]) is minimized. Return that minimum XOR sum.

For example, with nums1 = [1, 0, 3] and nums2 = [5, 3, 4], rearranging nums2 to [3, 4, 5] gives (1 XOR 3) + (0 XOR 4) + (3 XOR 5) = 2 + 4 + 6 = 12, which is optimal.

nums1 = [1, 0, 3], nums2 = [5, 3, 4]. Rearranging nums2 to [3, 4, 5] gives XOR sum = 2 + 4 + 6 = 12, which is optimal.

This is an assignment problem: you need to find the best one-to-one pairing between elements of nums1 and elements of nums2. With n up to 14, there are up to 14! possible permutations of nums2. Brute force is far too slow. The key insight is that bitmask DP lets you efficiently track which elements of nums2 have already been assigned, reducing the search space from O(n!) to O(n * 2^n).

Define dp[mask] as the minimum XOR sum achievable when the set of used elements from nums2 is described by mask. The number of set bits in mask tells you how many elements of nums1 have been paired so far, which means you are currently assigning nums1[popcount(mask)]. For each unused index j in nums2 (where bit j of mask is 0), you try pairing it and take the minimum.

The popcount trick is what makes bitmask DP elegant here. You do not need a separate variable to track which element of nums1 you are assigning. The mask itself encodes that information: if 3 bits are set, you have already assigned nums1[0], nums1[1], and nums1[2], so the next element to assign is nums1[3].

The code

def minimum_xor_sum(nums1, nums2):
    n = len(nums1)
    dp = [float('inf')] * (1 << n)
    dp[0] = 0

    for mask in range(1 << n):
        i = bin(mask).count('1')
        if i >= n:
            continue
        for j in range(n):
            if mask & (1 << j):
                continue
            new_mask = mask | (1 << j)
            dp[new_mask] = min(dp[new_mask], dp[mask] + (nums1[i] ^ nums2[j]))

    return dp[(1 << n) - 1]

The function initializes a DP array of size 2^n, where each entry corresponds to a subset of nums2 elements. Starting from dp[0] = 0 (no elements assigned, zero cost), it iterates through every mask. For each mask, it computes i as the number of set bits, which identifies the current nums1 index to assign. It then tries every unused nums2[j], updating dp[new_mask] with the XOR cost of that pairing. The answer lives at dp[(1 << n) - 1], which is the state where all elements have been assigned.

Practice bitmask DP patterns

Visual walkthrough

Step 1: State representation with bitmask

A bitmask tracks which elements of nums2 have been assigned. Bit i is 1 if nums2[i] is already paired. dp[mask] stores the minimum XOR sum using the assigned elements.

Step 2: Pair nums1[0] = 1 with each available nums2[j]

For nums1[0], try pairing with every unused element of nums2. The XOR cost varies by choice. The best first choice is nums2[1] = 3 with XOR cost 2.

Step 3: Recursive transitions

Each level assigns the next element of nums1. The number of set bits in mask tells you which nums1 index you are assigning. The DP explores all branches and caches results by mask.

Step 4: Optimal assignment found

The DP finds the minimum total: 1 XOR 3 + 0 XOR 4 + 3 XOR 5 = 2 + 4 + 6 = 12. The mask 0b111 confirms all elements of nums2 have been assigned.

The walkthrough shows how the DP explores different pairings. Each mask state represents a unique subset of assigned elements from nums2. The algorithm systematically tries every valid pairing and keeps only the minimum cost path to each state. Because many different orderings lead to the same mask, the DP avoids redundant computation by caching results per mask.

Complexity analysis

Metric	Value
Time	O(n * 2^n) where n is the array length
Space	O(2^n) for the DP table

There are 2^n possible masks. For each mask, you iterate over n possible choices for the next pairing. Each iteration does O(1) work (XOR, comparison, bit count). The space is dominated by the DP array of 2^n entries. With n up to 14, this gives roughly 14 * 16384 = 229,376 operations, which is very fast.

Drill DP problems with spaced repetition

Building blocks

Bitmask DP for assignment problems

Bitmask DP is the go-to technique when you need to find an optimal assignment between two sets and n is small (typically n up to 20). The bitmask encodes which elements from one set have been used. The popcount of the mask identifies the current position in the other set. This pattern appears in problems like the traveling salesman problem, task assignment, and matching problems. Once you recognize that the problem is asking for an optimal bijection between two small sets, bitmask DP should be your first thought.

XOR properties

XOR is a bitwise operation where each bit of the result is 1 if the corresponding bits of the two operands differ, and 0 if they are the same. Key properties include: a XOR a = 0, a XOR 0 = a, and XOR is both commutative and associative. In this problem, the XOR between two numbers measures how "different" they are in binary. Pairing numbers that share more common bits produces a smaller XOR. Understanding this helps build intuition for why certain pairings are better than others.

Edge cases

Single element arrays. When n = 1, there is only one possible pairing. The answer is simply nums1[0] XOR nums2[0]. The DP handles this naturally with just two mask states (0 and 1).

All elements identical. If every element in both arrays is the same value, every pairing produces 0 XOR 0 = 0 and the total is 0. The DP converges immediately since all transitions have zero cost.

n = 14 (maximum constraint). With n = 14, the DP table has 2^14 = 16384 entries. This is well within memory and time limits. The algorithm scales gracefully to the constraint boundary.

Large values. Elements can be up to 10^7. XOR of two large integers is still O(1) since it operates on fixed-width integers. The DP values stay bounded by n * max_xor, which fits comfortably in a 32-bit integer.

Arrays where original order is already optimal. Sometimes no rearrangement improves the XOR sum. The DP naturally discovers this by comparing the identity assignment against all alternatives.

From understanding to recall

The bitmask DP pattern for assignment problems is one of those techniques that feels natural once you see it, but can be hard to pull from memory during an interview. The critical details to remember are: the mask tracks which elements of one array are used, the popcount of the mask determines the index in the other array, and you iterate over all unset bits to try each valid pairing. Missing any of these pieces means you cannot write the solution.

Spaced repetition locks in the full pattern. You write the DP loop, the popcount trick, and the mask transitions from scratch today. A few days later you do it again. Each repetition makes the template more automatic. When you see an assignment problem with small n, the bitmask DP structure will surface immediately, and you will spend your interview time on problem-specific details rather than reconstructing the technique.

Try CodeBricks free

XOR Queries of a Subarray - Another problem leveraging XOR properties
Closest Subsequence Sum - Uses bitmask enumeration for subset problems
4Sum II - Another problem about optimal pairing across arrays