# Bitwise XOR of All Pairings
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/bitwise-xor-of-all-pairings)
Canonical: https://scaleengineer.com/dsa/problems/bitwise-xor-of-all-pairings
**Patterns:** [Bit Manipulation](https://scaleengineer.com/dsa/patterns/bit-manipulation)
**Data structures:** Array
**Companies:** [Trilogy](https://scaleengineer.com/companies/trilogy)
---
## Problem
You are given two **0-indexed** arrays, `nums1` and `nums2`, consisting of non-negative integers. Let there be another array, `nums3`, which contains the bitwise XOR of **all pairings** of integers between `nums1` and `nums2` (every integer in `nums1` is paired with every integer in `nums2` **exactly once**).

Return _the **bitwise XOR** of all integers in_ `nums3`.

**Example 1:**

**Input:** nums1 = [2,1,3], nums2 = [10,2,5,0]
**Output:** 13
**Explanation:**
A possible nums3 array is [8,0,7,2,11,3,4,1,9,1,6,3].
The bitwise XOR of all these numbers is 13, so we return 13.

**Example 2:**

**Input:** nums1 = [1,2], nums2 = [3,4]
**Output:** 0
**Explanation:**
All possible pairs of bitwise XORs are nums1[0] ^ nums2[0], nums1[0] ^ nums2[1], nums1[1] ^ nums2[0],
and nums1[1] ^ nums2[1].
Thus, one possible nums3 array is [2,5,1,6].
2 ^ 5 ^ 1 ^ 6 = 0, so we return 0.

**Constraints:**

* `1 <= nums1.length, nums2.length <= 105`
* `0 <= nums1[i], nums2[j] <= 109`

# Approaches
## Brute Force Simulation
This approach directly simulates the process described in the problem. We generate all possible pairings of elements from `nums1` and `nums2`, calculate the bitwise XOR for each pair, and then compute the bitwise XOR of all these results.
**Time:** O(N * M), where N is the length of `nums1` and M is the length of `nums2`. We iterate through every possible pair, making this quadratic in terms of input size. · **Space:** O(1), as we only use a few variables to store the intermediate and final results, regardless of the input size.
**Pros:** Simple to understand and implement.; Directly follows the problem description without requiring mathematical insights.
**Cons:** Highly inefficient for large inputs.; Will not pass the time limits for the given constraints, leading to a 'Time Limit Exceeded' (TLE) error.
### Explanation
This method involves a straightforward, brute-force implementation. We iterate through every element in `nums1` and, for each of those, we iterate through every element in `nums2`. This creates all possible pairs. For each pair `(num1, num2)`, we compute their bitwise XOR `num1 ^ num2` and accumulate this value into a running total XOR sum. While simple to conceptualize, its performance degrades rapidly as the size of the input arrays increases.

```java
class Solution {
    public int xorAllNums(int[] nums1, int[] nums2) {
        int xor_sum = 0;
        for (int num1 : nums1) {
            for (int num2 : nums2) {
                xor_sum ^= (num1 ^ num2);
            }
        }
        return xor_sum;
    }
}
```
### Algorithm
- Initialize a variable `xor_sum` to 0.
- Use a nested loop. The outer loop iterates through each element `num1` in `nums1`.
- The inner loop iterates through each element `num2` in `nums2`.
- Inside the inner loop, calculate the bitwise XOR of the current pair: `pair_xor = num1 ^ num2`.
- Update the `xor_sum` by XORing it with the `pair_xor`: `xor_sum = xor_sum ^ pair_xor`.
- After the loops complete, return `xor_sum`.

## Optimized Approach with XOR Properties
A more efficient approach leverages the properties of the bitwise XOR operation. Instead of calculating the XOR for every pair, we can analyze how many times each number from `nums1` and `nums2` contributes to the final XOR sum and simplify the calculation.
**Time:** O(N + M), where N is the length of `nums1` and M is the length of `nums2`. We iterate through each array at most once to compute their respective XOR sums. · **Space:** O(1), as we only use a few variables to store the lengths and XOR sums.
**Pros:** Extremely efficient and fast.; Scales linearly with the input size, making it suitable for large constraints.; Elegant solution based on mathematical properties.
**Cons:** Requires understanding the properties of bitwise XOR, which might not be immediately obvious.
### Explanation
The key insight is to use the associative and commutative properties of XOR (`a ^ b = b ^ a` and `a ^ (b ^ c) = (a ^ b) ^ c`). The total XOR sum is the XOR of `(num1 ^ num2)` for all `num1` in `nums1` and `num2` in `nums2`.

Let `m = nums1.length` and `n = nums2.length`.
Each element `num1` from `nums1` is paired with `n` elements from `nums2`. Thus, each `num1` appears `n` times in the total XOR sum expression.
Similarly, each element `num2` from `nums2` appears `m` times.

We know that `x ^ x = 0`. Therefore:
- If a number is XORed with itself an even number of times, the result is 0.
- If a number is XORed with itself an odd number of times, the result is the number itself.

So, the contribution of `nums1` to the total sum is the XOR sum of all its elements if `n` is odd, and 0 if `n` is even.
Likewise, the contribution of `nums2` is its total XOR sum if `m` is odd, and 0 if `m` is even.

The final result is the XOR of these two contributions.

```java
class Solution {
    public int xorAllNums(int[] nums1, int[] nums2) {
        int m = nums1.length;
        int n = nums2.length;

        int xor_sum1 = 0;
        if (n % 2 != 0) { // Each element in nums1 appears n (odd) times
            for (int num : nums1) {
                xor_sum1 ^= num;
            }
        }

        int xor_sum2 = 0;
        if (m % 2 != 0) { // Each element in nums2 appears m (odd) times
            for (int num : nums2) {
                xor_sum2 ^= num;
            }
        }

        return xor_sum1 ^ xor_sum2;
    }
}
```
### Algorithm
- Let `m` be the length of `nums1` and `n` be the length of `nums2`.
- Calculate `xor1`, the bitwise XOR sum of all elements in `nums1`.
- Calculate `xor2`, the bitwise XOR sum of all elements in `nums2`.
- Initialize a result variable `res` to 0.
- If `n` (length of `nums2`) is odd, it means each element of `nums1` contributes to the final sum. So, update `res = res ^ xor1`.
- If `m` (length of `nums1`) is odd, it means each element of `nums2` contributes to the final sum. So, update `res = res ^ xor2`.
- Return `res`.

# Solutions
### Python

```python
class Solution : def xorAllNums ( self , nums1 : List [ int ], nums2 : List [ int ]) -> int : ans = 0 if len ( nums2 ) & 1 : for v in nums1 : ans ^= v if len ( nums1 ) & 1 : for v in nums2 : ans ^= v return ans
```

### Java

```java
class Solution { public int xorAllNums ( int [] nums1 , int [] nums2 ) { int ans = 0 ; if ( nums2 . length % 2 == 1 ) { for ( int v : nums1 ) { ans ^= v ; } } if ( nums1 . length % 2 == 1 ) { for ( int v : nums2 ) { ans ^= v ; } } return ans ; } }
```

### CPP

```cpp
class Solution { public: int xorAllNums ( vector < int >& nums1 , vector < int >& nums2 ) { int ans = 0 ; if ( nums2 . size () % 2 == 1 ) { for ( int v : nums1 ) { ans ^= v ; } } if ( nums1 . size () % 2 == 1 ) { for ( int v : nums2 ) { ans ^= v ; } } return ans ; } };
```