Find XOR Sum of All Pairs Bitwise AND
HardPrompt
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 to1 XOR 2 XOR 3 XOR 4 = 4, and the XOR sum of[3]is equal to3.
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 <= 1050 <= arr1[i], arr2[j] <= 109
Approaches
2 approaches with complexity analysis and trade-offs.
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.
Algorithm
- Initialize a variable
xorSumto 0. - Use a nested loop to iterate through every element
num1inarr1and every elementnum2inarr2. - Inside the inner loop, calculate the bitwise AND of the pair:
num1 & num2. - Update
xorSumby XORing it with the result:xorSum ^= (num1 & num2). - After iterating through all pairs, return
xorSum.
Walkthrough
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.
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; }}Complexity
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.
Trade-offs
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.
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.
Algorithm
- Calculate the XOR sum of all elements in
arr1. Let's call itxorSum1. - Calculate the XOR sum of all elements in
arr2. Let's call itxorSum2. - The final result is the bitwise AND of these two XOR sums:
xorSum1 & xorSum2.
Walkthrough
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.
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; }}Complexity
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.
Trade-offs
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.
Solutions
Solution
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; }}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; }};class Solution: def getXORSum(self, arr1: List[int], arr2: List[int]) -> int: a = reduce(xor, arr1) b = reduce(xor, arr2) return a & bVideo walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.