Find XOR Sum of All Pairs Bitwise AND

Problem Description

Given two 0-indexed arrays arr1 and arr2 consisting of non-negative integers, return the XOR sum of the results of arr1[i] AND arr2[j] for every possible pair (i, j).

Key Insights

• The result of arr1[i] AND arr2[j] is influenced by the bits that are set in both arr1[i] and arr2[j].
• The XOR operation has properties that can be leveraged, including:
  • x XOR x = 0 for any integer x.
  • x XOR 0 = x for any integer x.
• Instead of computing all pairs explicitly, we can analyze the contribution of each bit position to the final result.

Space and Time Complexity

Time Complexity: O(32 * (n + m)), where n is the length of arr1 and m is the length of arr2, because we check each bit position (up to 32 bits for numbers <= 10^9) for all numbers in both arrays. Space Complexity: O(1), as we only use a constant amount of extra space for counting.

Solution

To solve the problem efficiently, we will iterate through each bit position (0 to 31) and count how many numbers in arr1 and arr2 have that particular bit set. For each bit position, we can calculate how many pairs will contribute to the final XOR sum by applying the AND operation.

1. For each bit position, count how many numbers in arr1 have the bit set (count1) and how many in arr2 have the bit set (count2).
2. The contribution of that bit to the final XOR sum can be determined by the formula: count1 * count2 (the number of pairs that will have that bit set in the result).
3. If this count is odd, then that bit will be set in the final result.

Code Solutions