# 1879.minimum-xor-sum-of-two-arrays

## Statement

• 比方说，`[1,2,3]` 和 `[3,2,1]` 的 异或值之和 等于 `(1 XOR 3) + (2 XOR 2) + (3 XOR 1) = 2 + 0 + 2 = 4` 。

``````输入：nums1 = [1,2], nums2 = [2,3]

``````输入：nums1 = [1,0,3], nums2 = [5,3,4]

``````

• `n == nums1.length`
• `n == nums2.length`
• `1 <= n <= 14`
• `0 <= nums1[i], nums2[i] <= 107`

• Link: Minimum XOR Sum of Two Arrays
• Difficulty: Hard
• Tag: `Bit Manipulation` `Array` `Dynamic Programming` `Bitmask`

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`

## Solution

``````from typing import List

class Solution:
def minimumXORSum(self, nums1: List[int], nums2: List[int]) -> int:
n = len(nums1)
f = [0x3f3f3f3f for i in range(1 << n)]
f[0] = 0
for S in range(1, 1 << n):
cnt = bin(S).count("1")

for i in range(n):
if (S >> i) & 1:
f[S] = min(f[S], f[S ^ (1 << i)] +
(nums1[cnt - 1] ^ nums2[i]))

return f[-1]
``````