What does 'Find XOR Sum of All Pairs Bitwise AND' mean?

It means calculating the XOR of every result obtained by ANDing each element from arr1 with each element from arr2 without generating all pairs explicitly.

Can this problem be solved without nested loops over both arrays?

Yes, by analyzing each bit independently and counting contributions from both arrays, the XOR sum can be computed in linear time per bit.

Why is (a&b) XOR (a&c) = a & (b XOR c) useful here?

This identity allows simplification across array elements, reducing computation from quadratic to linear per bit, which is critical for large arrays.

What are common mistakes when implementing this problem?

Naively computing all pairwise ANDs, ignoring higher bits, or miscounting set bits can all lead to wrong results or timeouts.

Does the solution handle very large arrays efficiently?

Yes, by iterating bit by bit and using counts, it avoids O(n*m) complexity and uses minimal extra space.

#1835

Hard

auto_awesome数组·数学

LeetCode 题解工作台

所有数对按位与结果的异或和

列表的异或和（ XOR sum ）指对所有元素进行按位 XOR 运算的结果。如果列表中仅有一个元素，那么其异或和就等于该元素。例如， [1,2,3,4] 的异或和等于 1 XOR 2 XOR 3 XOR 4 = 4 ，而 [3] 的异或和等于 3 。给你两个下标从 0 开始计…

数组数学位运算

题目描述

列表的 异或和（XOR sum）指对所有元素进行按位 XOR 运算的结果。如果列表中仅有一个元素，那么其 异或和 就等于该元素。

例如，[1,2,3,4] 的 异或和 等于 1 XOR 2 XOR 3 XOR 4 = 4 ，而 [3] 的 异或和 等于 3 。

给你两个下标 从 0 开始 计数的数组 arr1 和 arr2 ，两数组均由非负整数组成。

根据每个 (i, j) 数对，构造一个由 arr1[i] AND arr2[j]（按位 AND 运算）结果组成的列表。其中 0 <= i < arr1.length 且 0 <= j < arr2.length 。

返回上述列表的 异或和 。

示例 1：

输入：arr1 = [1,2,3], arr2 = [6,5]
输出：0
解释：列表 = [1 AND 6, 1 AND 5, 2 AND 6, 2 AND 5, 3 AND 6, 3 AND 5] = [0,1,2,0,2,1] ，
异或和 = 0 XOR 1 XOR 2 XOR 0 XOR 2 XOR 1 = 0 。

示例 2：

输入：arr1 = [12], arr2 = [4]
输出：4
解释：列表 = [12 AND 4] = [4] ，异或和 = 4 。

提示：

1 <= arr1.length, arr2.length <= 10⁵
0 <= arr1[i], arr2[j] <= 10⁹

lightbulb

解题思路

方法一：位运算

假设数组 $arr1$ 的元素分别为 $a_1, a_2, \cdots, a_n$ ，数组 $arr2$ 的元素分别为 $b_1, b_2, \cdots, b_m$ ，那么题目答案为：

\begin{aligned} \textit{ans} &= (a_1 \wedge b_1) \oplus (a_1 \wedge b_2) ... (a_1 \wedge b_m) \\ &\quad \oplus (a_2 \wedge b_1) \oplus (a_2 \wedge b_2) ... (a_2 \wedge b_m) \\ &\quad \oplus \cdots \\ &\quad \oplus (a_n \wedge b_1) \oplus (a_n \wedge b_2) ... (a_n \wedge b_m) \\ \end{aligned}

由于布尔代数中，异或运算就是不进位的加法，与运算就是乘法，所以上式可以简化为：

\textit{ans} = (a_1 \oplus a_2 \oplus \cdots \oplus a_n) \wedge (b_1 \oplus b_2 \oplus \cdots \oplus b_m)

即，数组 $arr1$ 的异或和与数组 $arr2$ 的异或和的与运算结果。

时间复杂度 $O(n + m)$ ，其中 $n$ 和 $m$ 分别为数组 $arr1$ 和 $arr2$ 的长度。空间复杂度 $O(1)$ 。

1

2

3

4

5

6

class Solution:
    def getXORSum(self, arr1: List[int], arr2: List[int]) -> int:
        a = reduce(xor, arr1)
        b = reduce(xor, arr2)
        return a & b

speed

复杂度分析

指标	值
时间	complexity is O(max_bit * (len(arr1) + len(arr2))) since each bit is evaluated across both arrays. Space complexity is O(1) additional memory beyond input arrays because we only track counts per bit.
空间	Depends on the final approach

psychology

面试官常问的追问

外企场景

question_mark
Expect recognition of bitwise simplification and avoidance of naive pair enumeration.
question_mark
Check for independent bit analysis using counts instead of generating full AND matrix.
question_mark
Listen for insight using (a&b) XOR (a&c) identity to optimize computation.

warning

常见陷阱

外企场景

error
Attempting to compute all pairwise ANDs explicitly leads to TLE for large arrays.
error
Overlooking bit positions beyond 30 can cause incorrect XOR sums for large numbers.
error
Failing to correctly multiply counts of set bits from both arrays may yield wrong results.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Compute XOR sum of all pairs using OR instead of AND.
arrow_right_alt
Find XOR sum of all triplet ANDs across three arrays.
arrow_right_alt
Calculate XOR sum of all pairwise ANDs but only for even indexed elements.

help

常见问题

外企场景

继续练习

#1863 找出所有子集的异或总和再求和 #1799 N 次操作后的最大分数和 #1994 好子集的数目