What is the key trick to solve Bitwise XOR of All Pairings efficiently?

The key is noticing that elements paired an even number of times cancel out, so only elements paired an odd number of times affect the final XOR.

Do I need to build all pair combinations in nums3?

No, building nums3 is unnecessary and inefficient; just compute XORs conditionally based on opposite array length parity.

Can this method handle arrays of length up to 100,000?

Yes, because the solution runs in O(n + m) time and uses O(1) extra space, suitable for large arrays.

What happens if both arrays have even lengths?

All elements pair an even number of times, so the final XOR is zero due to cancellation.

How does array plus bit manipulation pattern apply here?

The pattern is seen in computing XOR across pairs efficiently without explicit enumeration, leveraging bitwise properties and array length parity.

#2425

Medium

auto_awesome数组·结合·位运算·操作

LeetCode 题解工作台

所有数对的异或和

给你两个下标从 0 开始的数组 nums1 和 nums2 ，两个数组都只包含非负整数。请你求出另外一个数组 nums3 ，包含 nums1 和 nums2 中所有数对的异或和（ nums1 中每个整数都跟 nums2 中每个整数恰好匹配一次）。请你返回 nums3 中所有整数的异或和 …

数组位运算脑筋急转弯

题目描述

给你两个下标从 0 开始的数组 nums1 和 nums2 ，两个数组都只包含非负整数。请你求出另外一个数组 nums3 ，包含 nums1 和 nums2 中 所有数对 的异或和（nums1 中每个整数都跟 nums2 中每个整数恰好匹配一次）。

请你返回 nums3 中所有整数的 异或和 。

示例 1：

输入：nums1 = [2,1,3], nums2 = [10,2,5,0]
输出：13
解释：
一个可能的 nums3 数组是 [8,0,7,2,11,3,4,1,9,1,6,3] 。
所有这些数字的异或和是 13 ，所以我们返回 13 。

示例 2：

输入：nums1 = [1,2], nums2 = [3,4]
输出：0
解释：
所有数对异或和的结果分别为 nums1[0] ^ nums2[0] ，nums1[0] ^ nums2[1] ，nums1[1] ^ nums2[0] 和 nums1[1] ^ nums2[1] 。
所以，一个可能的 nums3 数组是 [2,5,1,6] 。
2 ^ 5 ^ 1 ^ 6 = 0 ，所以我们返回 0 。

提示：

1 <= nums1.length, nums2.length <= 10⁵
0 <= nums1[i], nums2[j] <= 10⁹

lightbulb

解题思路

方法一：脑筋急转弯 + 位运算

由于数组的每个元素都会与另一个数组的每个元素进行异或，我们知道，同一个数异或两次，结果不变，即 $a \oplus a = 0$ 。因此，我们只需要统计数组的长度，就能知道每个元素与另一个数组的每个元素进行异或的次数。

如果 nums2 数组长度为奇数，那么相当于 nums1 中每个元素都与 nums2 中的每个元素进行了奇数次异或，因此 nums1 数组的最终异或结果即为 nums1 数组的所有元素异或的结果。如果为偶数，那么相当于 nums1 中每个元素都与 nums2 中的每个元素进行了偶数次异或，因此 nums1 数组的最终异或结果为 0。

同理，我们可以得知 nums2 数组的最终异或结果。

最终把两个异或结果再异或一次，即可得到最终结果。

时间复杂度 $O(m+n)$ 。其中 $m$ 和 $n$ 分别为数组 nums1 和 nums2 的长度。

1

2

3

4

5

6

7

8

9

10

11

class Solution:
    def xorAllNums(self, nums1: List[int], nums2: List[int]) -> int:
        ans = 0
        if len(nums2) & 1:
            for v in nums1:
                ans ^= v
        if len(nums1) & 1:
            for v in nums2:
                ans ^= v
        return ans

speed

复杂度分析

指标	值
时间	complexity is O(n + m) because we iterate through nums1 and nums2 once. Space complexity is O(1) since no additional arrays proportional to input sizes are created.
空间	O(1)

psychology

面试官常问的追问

外企场景

question_mark
Watch if candidate suggests generating all pairs; it signals they might not notice XOR parity optimization.
question_mark
Check whether candidate identifies the cancellation pattern when array lengths are even.
question_mark
See if candidate applies the XOR accumulation technique without extra space.

warning

常见陷阱

外企场景

error
Generating nums3 explicitly leads to TLE for large arrays.
error
Ignoring array length parity causes incorrect XOR results.
error
Applying XOR naively without considering cancellation can mislead the computation.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Compute XOR of all pairwise sums instead of XORs between two arrays.
arrow_right_alt
Find the XOR of pairings where nums1 and nums2 may include negative integers.
arrow_right_alt
Determine XOR across multiple arrays in a chain of pairings, testing extension of parity logic.

help

常见问题

外企场景

继续练习

#2419 按位与最大的最长子数组 #2568 最小无法得到的或值 #2433 找出前缀异或的原始数组