What is the primary pattern for the 'Minimum XOR Sum of Two Arrays' problem?

The primary pattern for this problem is dynamic programming with bitmasking. The state transitions between subsets of nums2, evaluating the XOR sum for each pairing.

How do bitmasks help in solving this problem?

Bitmasks are used to represent the state of paired elements from nums2. Each bit indicates whether a particular element has been paired, enabling efficient state transitions during the dynamic programming process.

What is the time complexity of the solution for this problem?

The time complexity is O(n * 2^n), where n is the length of the arrays. This comes from iterating through all 2^n possible states and performing calculations for each.

What is the maximum length of the arrays nums1 and nums2?

The maximum length of both arrays nums1 and nums2 is 14, which allows for feasible computation using bitmasking and dynamic programming.

What common mistakes should I avoid while solving this problem?

Common mistakes include incorrectly managing the bitmask, overlooking the efficiency of dynamic programming, and mishandling state transitions between subsets of nums2.

#1879

Hard

auto_awesome状态·转移·动态规划

LeetCode 题解工作台

两个数组最小的异或值之和

给你两个整数数组 nums1 和 nums2 ，它们长度都为 n 。两个数组的异或值之和为 (nums1[0] XOR nums2[0]) + (nums1[1] XOR nums2[1]) + ... + (nums1[n - 1] XOR nums2[n - 1]) （下标从 0 开始 …

数组动态规划位运算位掩码

题目描述

给你两个整数数组 nums1 和 nums2 ，它们长度都为 n 。

两个数组的 异或值之和 为 (nums1[0] XOR nums2[0]) + (nums1[1] XOR nums2[1]) + ... + (nums1[n - 1] XOR nums2[n - 1]) （下标从 0 开始）。

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

请你将 nums2 中的元素重新排列，使得 异或值之和 最小。

请你返回重新排列之后的 异或值之和 。

示例 1：

输入：nums1 = [1,2], nums2 = [2,3]
输出：2
解释：将 nums2 重新排列得到 [3,2] 。
异或值之和为 (1 XOR 3) + (2 XOR 2) = 2 + 0 = 2 。

示例 2：

输入：nums1 = [1,0,3], nums2 = [5,3,4]
输出：8
解释：将 nums2 重新排列得到 [5,4,3] 。
异或值之和为 (1 XOR 5) + (0 XOR 4) + (3 XOR 3) = 4 + 4 + 0 = 8 。

提示：

n == nums1.length
n == nums2.length
1 <= n <= 14
0 <= nums1[i], nums2[i] <= 10⁷

lightbulb

解题思路

方法一：状态压缩动态规划

我们注意到 $n \leq 14$ ，因此，我们可以考虑使用状态压缩动态规划的方法求解本题。

我们用一个长度为 $n$ 的二进制数表示当前的状态，第 $i$ 位为 $1$ 表示 $nums2[i]$ 已经被选择，为 $0$ 表示 $nums2[i]$ 还未被选择。

我们定义 $f[i][j]$ 表示 $nums1$ 的前 $i$ 个数中，选择了 $nums2$ 的 $i$ 个数，且当前所选数字的状态为 $j$ 时，数组 $nums1$ 和 $nums2$ 的异或值之和的最小值。初始时 $f[0][0]=0$ ，其余 $f[i][j]=+\infty$ 。

我们可以枚举 $nums1$ 的第 $i$ 个数 $x$ ，然后在 $[0,2^n)$ 的范围内枚举状态 $j$ ，转移方程为 $f[i][j]=\min(f[i][j],f[i-1][j\oplus 2^k]+(x\oplus nums2[k]))$ ，其中 $k$ 是 $j$ 的二进制表示中的某个 $1$ 所在的位置。

最后答案为 $f[n][2^n-1]$ 。

时间复杂度 $O(n^2 \times 2^n)$ ，空间复杂度 $O(n \times 2^n)$ 。其中 $n$ 是数组的长度。

我们注意到，状态 $f[i][j]$ 只与 $f[i-1][j\oplus 2^k]$ 有关，因此我们去掉第一维，将空间复杂度优化到 $O(2^n)$ 。

1

2

3

4

5

6

7

8

9

10

11

12

class Solution:
    def minimumXORSum(self, nums1: List[int], nums2: List[int]) -> int:
        n = len(nums2)
        f = [[inf] * (1 << n) for _ in range(n + 1)]
        f[0][0] = 0
        for i, x in enumerate(nums1, 1):
            for j in range(1 << n):
                for k in range(n):
                    if j >> k & 1:
                        f[i][j] = min(f[i][j], f[i - 1][j ^ (1 << k)] + (x ^ nums2[k]))
        return f[-1][-1]

speed

复杂度分析

指标	值
时间	Depends on the final approach
空间	Depends on the final approach

psychology

面试官常问的追问

外企场景

question_mark
Check if the candidate understands the concept of dynamic programming with bitmasking.
question_mark
Look for a candidate's ability to handle small n values efficiently using DP.
question_mark
Assess whether the candidate can explain the trade-off of using DP over brute force permutations.

warning

常见陷阱

外企场景

error
Forgetting to properly manage the bitmask when updating the DP state.
error
Overlooking the fact that bitmasking can reduce time complexity exponentially, so brute-forcing is inefficient.
error
Incorrectly handling the transition between different DP states, leading to wrong XOR sums.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Consider alternative bitmask approaches for larger values of n (though the complexity may not scale well).
arrow_right_alt
Explore greedy algorithms or heuristics for larger inputs, but note the trade-offs in terms of optimality.
arrow_right_alt
Optimize for space by reducing the size of the DP table when dealing with sparse subsets.

help

常见问题

外企场景

继续练习

#1815 得到新鲜甜甜圈的最多组数 #1947 最大兼容性评分和 #1799 N 次操作后的最大分数和