Find XOR Sum of All Pairs Bitwise AND
Hard · Bit Manipulation · Array · Math · Bit Manipulation
Problem
You are given two arrays of non-negative integers, arr1 and arr2. For every pair (i, j), one index from each array, form arr1[i] AND arr2[j].
Return the XOR of all of those AND values. The XOR of a single value is that value.
Both arrays can hold 10^5 values, so there can be 10^10 pairs: listing them one by one is too slow.
Examples
Input: arr1 = [3,5], arr2 = [6,1] Output: 6
The ANDs are 3 & 6 = 2, 3 & 1 = 1, 5 & 6 = 4 and 5 & 1 = 1, and 2 ^ 1 ^ 4 ^ 1 = 6.
Input: arr1 = [9], arr2 = [9] Output: 9
There is one pair, and 9 & 9 = 9.
Input: arr1 = [1,1], arr2 = [1] Output: 0
Both pairs give 1, and 1 ^ 1 = 0.
Constraints
- 1 <= len(arr1), len(arr2) <= 10^5
- 0 <= arr1[i], arr2[j] <= 10^9
Approaches
- Baseline: every pair — time O(n · m), space O(1)
Follow-up
The same per-bit parity argument handles other pairings. The use cases ask for the XOR of all pairwise ORs, where the bit count becomes "all pairs minus the pairs with both bits clear", and for the plain sum of all pairwise ANDs, where you need the counts themselves, not just their parity.
Related problems
Start free on Cariara · Coding problems · System design studio
