Problem Description

Given two integer arrays arr1 and arr2, the task is to compute the XOR sum of the bitwise ANDs of all possible pairs, where each pair consists of one element from arr1 and one from arr2. In formal terms, for every possible pair (i, j) where 0 ≤ i < arr1.length and 0 ≤ j < arr2.length, calculate arr1[i] & arr2[j], then take the XOR of all these results.

The function signature is typically:
int getXORSum(int[] arr1, int[] arr2)

• Each element in the arrays is a non-negative integer.
• Elements can be reused in multiple pairs.
• Both arrays can be of different lengths.
• The answer must be computed efficiently for large arrays.

Thought Process

At first glance, the problem seems to require generating all possible pairs between the two arrays, computing the bitwise AND for each, and then XOR-ing all those results together. This direct approach would involve two nested loops and could be very slow if the arrays are large.

However, bitwise operations often have properties that can be exploited for optimization. The key is to look for patterns or mathematical properties that allow us to avoid explicitly iterating through every pair. By analyzing how XOR and AND interact, we might be able to simplify the computation.

The challenge is to find a way to compute the result without the brute-force double loop, making the solution scalable to large input sizes.

Solution Approach

Let's break down the steps to solve the problem efficiently:

1. Brute-force approach: For every element in arr1, AND it with every element in arr2, collect all results, and XOR them together. This is O(N*M) time, where N and M are the lengths of the arrays.
2. Bitwise observation: The XOR of all pairwise ANDs can be rewritten using properties of XOR and AND. For each bit position, the number of times a bit is set in the result is determined by the number of times it's set in arr1 and arr2.
3. Key insight: It turns out that the XOR sum of all arr1[i] & arr2[j] is equal to (arr1[0] ^ arr1[1] ^ ... ^ arr1[n-1]) & (arr2[0] ^ arr2[1] ^ ... ^ arr2[m-1]). In other words, XOR all elements in arr1 to get x1, XOR all elements in arr2 to get x2, and then compute x1 & x2.
4. Why does this work? Because XOR distributes over AND in the context of all pairs, and the commutative and associative properties of XOR and AND allow us to simplify the nested operations into a single expression.
5. Algorithm:
   • Compute the XOR of all elements in arr1 (call this x1).
   • Compute the XOR of all elements in arr2 (call this x2).
   • Return x1 & x2 as the answer.

This reduces the time complexity to O(N + M), making it highly efficient.

Example Walkthrough

Let's consider an example:

arr1 = [1, 2, 3]
arr2 = [6, 5]

1. Compute XOR of arr1:
   1 ^ 2 ^ 3 = (1 ^ 2) ^ 3 = 3 ^ 3 = 0
2. Compute XOR of arr2:
   6 ^ 5 = 3
3. Final answer is 0 & 3 = 0

Let's verify with brute-force:
All pairs and their ANDs:

• 1 & 6 = 0
• 1 & 5 = 1
• 2 & 6 = 2
• 2 & 5 = 0
• 3 & 6 = 2
• 3 & 5 = 1

The optimized approach matches the brute-force result.

Time and Space Complexity

• Brute-force approach:
  • Time Complexity: O(N*M) (for every element in arr1 and arr2)
  • Space Complexity: O(1) (if we XOR as we go and don't store intermediate results)
• Optimized approach:
  • Time Complexity: O(N + M) (one pass through each array to compute XORs)
  • Space Complexity: O(1) (only two integers needed for intermediate XORs)

The optimized solution is much more efficient and suitable for large input sizes.

Summary

The core insight for this problem is that the XOR sum of all pairwise ANDs between two arrays can be dramatically simplified using properties of bitwise operations. Instead of iterating over all pairs, we can just XOR all elements in each array, and then AND the two results. This makes the solution both elegant and highly efficient, reducing the time complexity from quadratic to linear.

Code Implementation

def getXORSum(arr1, arr2):
    xor1 = 0
    for num in arr1:
        xor1 ^= num
    xor2 = 0
    for num in arr2:
        xor2 ^= num
    return xor1 & xor2
      

class Solution {
public:
    int getXORSum(vector<int>& arr1, vector<int>& arr2) {
        int xor1 = 0, xor2 = 0;
        for (int num : arr1) xor1 ^= num;
        for (int num : arr2) xor2 ^= num;
        return xor1 & xor2;
    }
};
      

class Solution {
    public int getXORSum(int[] arr1, int[] arr2) {
        int xor1 = 0, xor2 = 0;
        for (int num : arr1) xor1 ^= num;
        for (int num : arr2) xor2 ^= num;
        return xor1 & xor2;
    }
}
      

var getXORSum = function(arr1, arr2) {
    let xor1 = 0, xor2 = 0;
    for (let num of arr1) xor1 ^= num;
    for (let num of arr2) xor2 ^= num;
    return xor1 & xor2;
};