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

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