Find XOR Sum of All Pairs Bitwise AND — Problem & Solution
Find XOR Sum of All Pairs Bitwise AND solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A hard problem.
Find XOR Sum of All Pairs Bitwise AND is a hard coding problem on arrays, math and bit manipulation, asked in Amazon and Google interviews.
- Difficulty: Hard
- Topics: Arrays, Math, Bit Manipulation
- Asked at: Amazon, Google
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
The XOR sum of a list is the bitwise XOR of all its elements (a one-element list's XOR sum is that element).
You are given two non-negative integer arrays arr1 and arr2. Form the list that holds arr1[i] AND arr2[j] for every pair (i, j) with 0 <= i < arr1.length and 0 <= j < arr2.length.
Return the XOR sum of that list.
Example 1
Input: arr1 = [3,5], arr2 = [6]
Output: 6
Explanation: The list is `[3 AND 6, 5 AND 6] = [2,4]`, and `2 XOR 4 = 6`.
Example 2
Input: arr1 = [12], arr2 = [4]
Output: 4
Example 3
Input: arr1 = [1,2,3], arr2 = [6,5]
Output: 0
Explanation: The list is `[0,1,2,0,2,1]`; every value appears twice, so the XOR sum is 0.
Constraints
1 <= arr1.length, arr2.length <= 10^50 <= arr1[i], arr2[j] <= 10^9
Hints for Find XOR Sum of All Pairs Bitwise AND
Hint 1
There are up to 10^10 pairs, so the list can never be built.
Hint 2
Look at one bit position at a time: AND and XOR both work bit by bit.
Hint 3
AND distributes over XOR:
(a1 AND b) XOR (a2 AND b) = (a1 XOR a2) AND b. Apply it to both arrays.
How to solve Find XOR Sum of All Pairs Bitwise AND
AND distributes over XOR exactly like multiplication over addition in arithmetic mod 2, so the XOR of all pairwise ANDs collapses to XOR(arr1) AND XOR(arr2).
Approach
- Compute
x, the XOR of every element ofarr1. - Compute
y, the XOR of every element ofarr2. - Return
x AND y.
Why it works
Fix one bit. In that bit, AND is multiplication and XOR is addition modulo 2. The XOR over all pairs is then the sum over i and j of a_i * b_j mod 2, which factors as (sum of a_i) * (sum of b_j) mod 2 — the bit of XOR(arr1) times the bit of XOR(arr2). Every bit behaves independently, so the identity holds for whole numbers.
Complexity
- Time —
O(n + m) - Space —
O(1)
Pitfalls
- The double loop is correct but does up to 10^10 operations.
- XOR the arrays first and AND once at the end — ANDing element by element and then XORing is a different expression.
- The result is below 2^30, so no wide integers are needed.
Reference solution
Python
from typing import List
def getXORSum(arr1: List[int], arr2: List[int]) -> int:
x = 0
for v in arr1:
x ^= v
y = 0
for v in arr2:
y ^= v
return x & yJava
public static int getXORSum(int[] arr1, int[] arr2) {
int x = 0, y = 0;
for (int v : arr1) x ^= v;
for (int v : arr2) y ^= v;
return x & y;
}C++
int getXORSum(vector<int>& arr1, vector<int>& arr2) {
int x = 0, y = 0;
for (int v : arr1) x ^= v;
for (int v : arr2) y ^= v;
return x & y;
}JavaScript
var getXORSum = function(arr1, arr2) {
var x = 0, y = 0;
for (var i = 0; i < arr1.length; i++) x ^= arr1[i];
for (var j = 0; j < arr2.length; j++) y ^= arr2[j];
return x & y;
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 1199 arrays problems · the whole catalogue
Learn the technique: Arrays · Bit Manipulation