Skip to content

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 to 1 XOR 2 XOR 3 XOR 4 = 4, and the XOR sum of [3] is equal to 3.

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

Thinking

We need \(\bigoplus_{i,j}(arr1[i]\wedge arr2[j])\). Enumerating pairs is impossible for lengths up to \(10^5\).

Bitwise, AND behaves like multiplication and XOR like addition without carry, so the expression equals \((\bigoplus arr1)\wedge(\bigoplus arr2)\). XOR each array and AND the two results.

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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
class Solution {
    public int getXORSum(int[] arr1, int[] arr2) {
        int a = 0, b = 0;
        for (int v : arr1) {
            a ^= v;
        }
        for (int v : arr2) {
            b ^= v;
        }
        return a & b;
    }
}

1
2
3
4
5
6
7
8
class Solution {
public:
    int getXORSum(vector<int>& arr1, vector<int>& arr2) {
        int a = accumulate(arr1.begin(), arr1.end(), 0, bit_xor<int>());
        int b = accumulate(arr2.begin(), arr2.end(), 0, bit_xor<int>());
        return a & b;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
func getXORSum(arr1 []int, arr2 []int) int {
    var a, b int
    for _, v := range arr1 {
        a ^= v
    }
    for _, v := range arr2 {
        b ^= v
    }
    return a & b
}

1
2
3
4
5
function getXORSum(arr1: number[], arr2: number[]): number {
    const a = arr1.reduce((acc, x) => acc ^ x);
    const b = arr2.reduce((acc, x) => acc ^ x);
    return a & b;
}

Comments