跳转至

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

问题描述#

列表的 异或和（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 <= 105
  • 0 <= arr1[i], arr2[j] <= 109

解题思路#

这道题如果猜测 "与" 运算对于 "异或" 运算的分配律成立的话，就很容易通过，虽然事实上证明结论的成立也很简单。

方法一#

  • \(AB=A \cdot B\) 表示 A and B
  • \(A+B\) 表示 A or B
  • \(\bar{A}\) 表示 not A
  • \(A \oplus B = \bar{A}B + A\bar{B}\) 表示 A xor B
\[ \begin{aligned} (AB) \oplus (AC) &= \overline{AB}AC + AB\overline{AC} \\ &=(\bar{A}+\bar{B})AC + AB(\bar{A}+\bar{C}) \\ &=A\bar{B}C+AB\bar{C}\\ &=A(\bar{B}C+B\bar{C})=A(B \oplus C) \end{aligned} \]

所以：

\[ \overset{n_a-1}{\underset{i=0}{\oplus}}\overset{n_b-1}{\underset{j=0}{\oplus}}A_i \cdot B_j = \overset{n_a-1}{\underset{i=0}{\oplus}}A_i \cdot \left(\overset{n_b-1}{\underset{j=0}{\oplus}}B_j\right) = \left(\overset{n_a-1}{\underset{i=0}{\oplus}}A_i\right) \cdot \left(\overset{n_b-1}{\underset{j=0}{\oplus}}B_j\right) \]
1
2
3
class Solution:
    def getXORSum(self, arr1: List[int], arr2: List[int]) -> int:
        return reduce(lambda x, y: x ^ y, arr1) & reduce(lambda x, y: x ^ y, arr2)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
class Solution {
public:
    int getXORSum(vector<int>& arr1, vector<int>& arr2) {
        auto xorsum = [] (vector<int> &arr) {
            int res = 0;
            for (int x : arr) {
                res ^= x;
            }
            return res;
        };
        return xorsum(arr1) & xorsum(arr2);
    }
};

时间复杂度：\(\mathcal{O}(m+n)\)
空间复杂度：\(\mathcal{O}(1)\)

方法二#

考虑最后结果的每一位的取值是 0 还是 1。

假设最后进行异或的结果的某一位上有 \(m\) 个 0，\(n\) 个 1，因为 0 对异或结果没有影响，所以只用考虑该位上 1 的个数。

如果 \(n\) 为奇数，则该位为 1，否则该位为 0。所以最后的答案只要将所有有奇数个 1 的位的权重相加即可。

然后就是如何获取每一位为 1 的个数。因为是相与的结果，所以结果就是 arr1 中某一位为 1 的个数 \(a\) 乘以 arr2 中相同的位为 1 的个数 \(b\) 即可，然后如果 \(a \times b\) 是个奇数，则答案加上这个位的权重。

如果乘积为奇数，则说明 \(a,b\) 都为奇数。 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
class Solution:
    def getXORSum(self, arr1: List[int], arr2: List[int]) -> int:
        ans = 0
        for i in range(31):
            f = False
            for x in arr1:
                f ^= (x >> i) & 1
            if not f: continue

            f = False
            for x in arr2:
                f ^= (x >> i) & 1
            if not f: continue

            ans |= 1 << i
        return ans

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
public:
    int getXORSum(vector<int>& arr1, vector<int>& arr2) {
        int ans = 0;
        for (int i = 0; i <= 30; ++i) {
            bool f = 0;
            for (int x : arr1) {
                f ^= (x >> i) & 1;
            }
            if (!f) continue;

            f = 0;
            for (int x : arr2) {
                f ^= (x >> i) & 1;
            }
            if (!f) continue;

            ans |= 1 << i;
        }
        return ans;
    }
};

时间复杂度：\(\mathcal{O}(31\times(m+n))\)
空间复杂度：\(\mathcal{O}(1)\)

返回顶部

在手机上阅读