# Find XOR Sum of All Pairs Bitwise AND
**Difficulty:** HARD
[External](https://leetcode.com/problems/find-xor-sum-of-all-pairs-bitwise-and)
Canonical: https://scaleengineer.com/dsa/problems/find-xor-sum-of-all-pairs-bitwise-and
**Patterns:** [Math](https://scaleengineer.com/dsa/patterns/math), [Bit Manipulation](https://scaleengineer.com/dsa/patterns/bit-manipulation)
**Data structures:** Array
---
## Problem
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`

# Approaches
## Brute Force Simulation
This approach directly translates the problem description into code. It calculates the bitwise AND for every possible pair of elements, one from `arr1` and one from `arr2`, and accumulates the XOR sum of these results. While straightforward, its performance is poor due to the nested iteration over the two arrays.
**Time:** O(N * M), where N is the length of `arr1` and M is the length of `arr2`. This is because of the nested loops that iterate through all possible pairs of elements from the two arrays. · **Space:** O(1) extra space. We only need a single variable to store the running XOR sum.
**Pros:** Simple to understand and implement as it follows the problem statement literally.; Requires no special knowledge of mathematical properties.
**Cons:** Extremely inefficient for large arrays, leading to a 'Time Limit Exceeded' error on most platforms for the given constraints.; The time complexity of O(N*M) makes it impractical for inputs where N and M are up to 10^5.
### Explanation
The brute-force method involves a direct simulation of the process. We start with an accumulator for the XOR sum, initialized to zero. Then, we iterate through each element in the first array, `arr1`. For each of these elements, we iterate through every element in the second array, `arr2`. In the body of this inner loop, we perform a bitwise AND operation on the current pair of elements. The result of this AND operation is then XORed with our accumulator. This process continues until all pairs `(arr1[i], arr2[j])` have been processed. The final value in the accumulator is the desired XOR sum.

```java
class Solution {
    public int getXORSum(int[] arr1, int[] arr2) {
        int xorSum = 0;
        for (int num1 : arr1) {
            for (int num2 : arr2) {
                xorSum ^= (num1 & num2);
            }
        }
        return xorSum;
    }
}
```
### Algorithm
- Initialize a variable `xorSum` to 0.
- Use a nested loop to iterate through every element `num1` in `arr1` and every element `num2` in `arr2`.
- Inside the inner loop, calculate the bitwise AND of the pair: `num1 & num2`.
- Update `xorSum` by XORing it with the result: `xorSum ^= (num1 & num2)`.
- After iterating through all pairs, return `xorSum`.

## Optimized Approach using Bitwise Properties
A much more efficient solution can be derived by using the properties of bitwise operations. The key insight is that the XOR sum of all pair-wise ANDs is equivalent to the AND of the XOR sums of the individual arrays. This is due to the distributive property of bitwise AND over bitwise XOR: `(a & c) ^ (b & c) = (a ^ b) & c`. This allows us to avoid the costly nested loop.
**Time:** O(N + M), where N is the length of `arr1` and M is the length of `arr2`. We iterate through each array once, which is a significant improvement over the brute-force approach. · **Space:** O(1) extra space. We only use two variables to store the XOR sum of each array.
**Pros:** Highly efficient with a linear time complexity.; Optimal solution that easily passes the given constraints.; Demonstrates an elegant application of bitwise properties.
**Cons:** The logic is not immediately obvious and requires understanding the distributive property of bitwise AND over XOR.
### Explanation
This optimized approach relies on a mathematical property of bitwise operations. The expression we need to compute is `XOR_{i,j} (arr1[i] & arr2[j])`.

We can rewrite this as:
`XOR_i (XOR_j (arr1[i] & arr2[j]))`

Let's analyze the inner XOR sum for a fixed `i`: `(arr1[i] & arr2[0]) ^ (arr1[i] & arr2[1]) ^ ...`
Using the distributive property `a & (b ^ c) = (a & b) ^ (a & c)`, this simplifies to:
`arr1[i] & (arr2[0] ^ arr2[1] ^ ...)`
This is `arr1[i] & (XOR sum of arr2)`.

Now, substituting this back, the full expression becomes:
`XOR_i (arr1[i] & (XOR sum of arr2))`
Applying the distributive property again:
`(arr1[0] ^ arr1[1] ^ ...) & (XOR sum of arr2)`

This simplifies the entire problem to finding the XOR sum of `arr1`, finding the XOR sum of `arr2`, and then taking the bitwise AND of these two results. This reduces the complexity from quadratic to linear.

```java
class Solution {
    public int getXORSum(int[] arr1, int[] arr2) {
        int xorSum1 = 0;
        for (int num : arr1) {
            xorSum1 ^= num;
        }
        
        int xorSum2 = 0;
        for (int num : arr2) {
            xorSum2 ^= num;
        }
        
        return xorSum1 & xorSum2;
    }
}
```
### Algorithm
- Calculate the XOR sum of all elements in `arr1`. Let's call it `xorSum1`.
- Calculate the XOR sum of all elements in `arr2`. Let's call it `xorSum2`.
- The final result is the bitwise AND of these two XOR sums: `xorSum1 & xorSum2`.

# Solutions
### Java

```java
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;
  }
}

```

### CPP

```cpp
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;
  }
};

```

### Python

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

```