# 1879. Minimum XOR Sum of Two Arrays

Contents

## 题目

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`

## 思路

dp[0] = 0

——递推关系是否足够简洁很重要，直接决定了代码会不会TLE或者MLE。

## 代码

``````class Solution(object):
def minimumXORSum(self, nums1, nums2):
"""
:type nums1: List[int]
:type nums2: List[int]
:rtype: int
"""

N = len(nums1)

def count_bit(bits):
s = bin(bits)
return len([i for i in s if i == '1'])

l = [None] * (1 << len(nums1))
l[0] = 0
def dp(bits):
if l[bits] is not None:
return l[bits]
ret = None
idx = count_bit(bits) - 1
for i in range(len(nums1)):
if (1 << i) & bits == 0:
continue
cur_ans = (nums1[idx] ^ nums2[i]) + dp(bits & ~(1 << i))
ret = cur_ans if ret is None else min(cur_ans, ret)
l[bits] = ret
return ret

return dp((1 << len(nums1)) - 1)``````

## 神仙代码

``````from scipy.optimize import linear_sum_assignment as LSA

class Solution(object):
def minimumXORSum(self, nums1, nums2):
cost = [[x^y for y in nums2] for x in nums1]
return sum(cost[x][y] for x,y in zip(*LSA(cost)))``````

——此处是内容的分割线——