1835. Find XOR Sum of All Pairs Bitwise AND
Description
The XOR sum of a list is the bitwise XOR
of all its elements. If the list only contains one element, then its XOR sum will be equal to this element.
- For example, the XOR sum of
[1,2,3,4]
is equal to1 XOR 2 XOR 3 XOR 4 = 4
, and the XOR sum of[3]
is equal to3
.
You are given two 0-indexed arrays arr1
and arr2
that consist only of non-negative integers.
Consider the list containing the result of arr1[i] AND arr2[j]
(bitwise AND
) for every (i, j)
pair where 0 <= i < arr1.length
and 0 <= j < arr2.length
.
Return the XOR sum of the aforementioned list.
Example 1:
Input: arr1 = [1,2,3], arr2 = [6,5] Output: 0 Explanation: The list = [1 AND 6, 1 AND 5, 2 AND 6, 2 AND 5, 3 AND 6, 3 AND 5] = [0,1,2,0,2,1]. The XOR sum = 0 XOR 1 XOR 2 XOR 0 XOR 2 XOR 1 = 0.
Example 2:
Input: arr1 = [12], arr2 = [4] Output: 4 Explanation: The list = [12 AND 4] = [4]. The XOR sum = 4.
Constraints:
1 <= arr1.length, arr2.length <= 105
0 <= arr1[i], arr2[j] <= 109
Solutions
Solution 1: Bitwise Operation
Assume that the elements of array $arr1$ are $a_1, a_2, ..., a_n$, and the elements of array $arr2$ are $b_1, b_2, ..., b_m$. Then, the answer to the problem is:
$$ \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} $$
Since in Boolean algebra, the XOR operation is addition without carry, and the AND operation is multiplication, the above formula can be simplified as:
$$ \textit{ans} = (a_1 \oplus a_2 \oplus \cdots \oplus a_n) \wedge (b_1 \oplus b_2 \oplus \cdots \oplus b_m) $$
That is, the bitwise AND of the XOR sum of array $arr1$ and the XOR sum of array $arr2$.
The time complexity is $O(n + m)$, where $n$ and $m$ are the lengths of arrays $arr1$ and $arr2$, respectively. The space complexity is $O(1)$.
1 2 3 4 5 |
|
1 2 3 4 5 6 7 8 9 10 11 12 |
|
1 2 3 4 5 6 7 8 |
|
1 2 3 4 5 6 7 8 9 10 |
|
1 2 3 4 5 |
|