Watch 10 video solutions for Find XOR Sum of All Pairs Bitwise AND, a hard level problem involving Array, Math, Bit Manipulation. This walkthrough by Happy Coding has 1,365 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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.
[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 <= 1050 <= arr1[i], arr2[j] <= 109Problem Overview: You are given two integer arrays arr1 and arr2. For every pair (i, j), compute arr1[i] & arr2[j], then XOR all those results together. A direct nested loop works but is expensive. The key observation is that XOR and AND operations follow distributive properties that let you collapse the entire computation.
Approach 1: Brute Force Pair Enumeration (Time: O(n*m), Space: O(1))
The straightforward method iterates through every pair of elements from the two arrays. For each pair, compute arr1[i] & arr2[j] and XOR the result into an accumulator. This directly matches the definition of the problem and is easy to reason about. The downside is the nested iteration: if n and m are the array sizes, the algorithm performs n * m AND operations and XOR updates. This approach is mainly useful for understanding the problem or verifying results for small inputs.
The method relies only on basic operations from array traversal and bit manipulation. With large arrays, however, the quadratic growth makes it impractical for interview constraints.
Approach 2: Bitwise XOR Theorem (Time: O(n + m), Space: O(1))
The optimized solution uses a distributive property of XOR and AND: (a & b) ^ (a & c) = a & (b ^ c). Extending this property across all pairs shows that the XOR of all pairwise ANDs equals:
(arr1[0] ^ arr1[1] ^ ... ^ arr1[n-1]) & (arr2[0] ^ arr2[1] ^ ... ^ arr2[m-1])
Instead of evaluating every pair, compute the XOR of all elements in arr1 and the XOR of all elements in arr2. Finally, take the bitwise AND of those two values. Each array is scanned once, so the algorithm runs in linear time relative to the input size.
This works because XOR aggregates the contribution of each bit position independently. When expanded algebraically, all pairwise terms collapse into the AND of the two cumulative XOR values. The technique is a common trick in bit manipulation and math-based interview problems where algebraic properties simplify large combinations.
Recommended for interviews: Interviewers expect the XOR theorem insight. Starting with the brute force approach shows you understand the definition of the problem, but recognizing the distributive property and reducing the complexity to O(n + m) demonstrates strong bit manipulation skills and mathematical reasoning.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force Pair Enumeration | O(n*m) | O(1) | Useful for understanding the definition of the problem or verifying correctness with small arrays |
| Bitwise XOR Theorem | O(n + m) | O(1) | Preferred solution for interviews and production due to linear time and constant space |