Find XOR Sum of All Pairs Bitwise AND

June 4, 20265 min read

leetcodeproblemhardarraysbit-manipulationmath

Given two integer arrays arr1 and arr2, compute the XOR of all values (arr1[i] AND arr2[j]) for every pair (i, j). In other words, take every combination of one element from arr1 and one from arr2, AND them together, then XOR all of those results into a single number.

This is LeetCode 1835: Find XOR Sum of All Pairs Bitwise AND. It looks like a nested loop problem at first glance, but a clean algebraic identity reduces it to linear time.

arr1 = [1, 2, 3], arr2 = [6, 5]. The brute-force computes AND for all 6 pairs, then XORs them. The identity reduces this to two XOR passes and one AND.

Why this problem matters

Bit manipulation problems in interviews often hinge on knowing a handful of identities. This problem tests one of the most powerful: AND distributes over XOR, just like multiplication distributes over addition in regular arithmetic. Once you recognize that distribution law, the brute-force O(n * m) approach collapses into O(n + m). Problems like this reward you for studying the algebraic properties of bitwise operators rather than just coding loops.

The key insight

The XOR of all pairwise ANDs equals (XOR of arr1) AND (XOR of arr2). That single identity is the entire solution. But why does it work?

Think about it bit by bit. For any bit position k, (arr1[i] AND arr2[j]) has a 1 at position k only when both arr1[i] and arr2[j] have a 1 there. If there are c1 values in arr1 with a 1 at bit k and c2 values in arr2 with a 1 at bit k, then c1 * c2 of the pair ANDs have a 1 at that bit.

XOR only cares about parity. XOR-ing c1 * c2 ones gives 1 if the product is odd and 0 if it is even. A product is odd only when both factors are odd. The parity of the count of 1s at bit k in arr1 is the same as bit k of XOR(arr1), because XOR accumulates parity. The same holds for arr2.

So the result bit at position k is 1 exactly when bit k of XOR(arr1) is 1 AND bit k of XOR(arr2) is 1. That is precisely XOR(arr1) AND XOR(arr2).

The key identity:

XOR over all (i, j) of (arr1[i] AND arr2[j])
  = (arr1[0] XOR arr1[1] XOR ... XOR arr1[n-1])
    AND
    (arr2[0] XOR arr2[1] XOR ... XOR arr2[m-1])

The solution

from functools import reduce
from operator import xor

def get_xor_sum(arr1: list[int], arr2: list[int]) -> int:
    return reduce(xor, arr1) & reduce(xor, arr2)

This computes the XOR of all elements in arr1, the XOR of all elements in arr2, and returns their AND. Three lines, no nested loops.

Why is this valid? The proof boils down to the distribution law: a AND (b XOR c) = (a AND b) XOR (a AND c). You can expand the full expression using this rule. Start with a single element arr1[0] ANDed with every element of arr2:

arr1[0] AND arr2[0] XOR arr1[0] AND arr2[1] XOR ...
  = arr1[0] AND (arr2[0] XOR arr2[1] XOR ...)
  = arr1[0] AND XOR(arr2)

Now XOR across all elements of arr1:

(arr1[0] AND XOR(arr2)) XOR (arr1[1] AND XOR(arr2)) XOR ...
  = (arr1[0] XOR arr1[1] XOR ...) AND XOR(arr2)
  = XOR(arr1) AND XOR(arr2)

The second step uses the same distribution law in reverse, factoring out XOR(arr2).

AND distributes over XOR the same way multiplication distributes over addition. If you remember this one fact, problems that look like they need O(n * m) brute force often collapse to O(n + m). This distribution property is worth memorizing as a core bit manipulation building block.

Practice bit manipulation patterns with spaced repetition

Visual walkthrough

Step 1: Think bit by bit. Focus on bit position k.

If we can prove the identity for each bit position independently, it holds for the entire number. Let's examine bit position 0 (the least significant bit).

Step 2: How many pair ANDs have a 1 at bit position 0?

(arr1[i] AND arr2[j]) has a 1 at bit k only when both arr1[i] and arr2[j] have a 1 at bit k. So the count of 1s = (count of 1s in arr1) * (count of 1s in arr2).

Step 3: XOR cares only about parity (odd vs even count).

XOR of n copies of 1 is 1 if n is odd, 0 if n is even. So the result bit = 1 only when the count of pair ANDs with a 1 at that bit is odd.

Step 4: When is count1_arr1 * count1_arr2 odd?

A product is odd only when both factors are odd. The parity of the count of 1s at bit k in arr1 is exactly bit k of XOR(arr1). Same for arr2.

Step 5: This holds for every bit position, so the identity holds.

Since each bit is independent, we can combine them: XOR of all pair ANDs = XOR(arr1) AND XOR(arr2). Done in O(n + m) time.

The five steps above show that the identity holds at every bit position independently. Since each bit contributes to the final answer on its own, the full-number identity follows directly.

Complexity analysis

Approach	Time	Space
XOR reduction + AND	O(n + m)	O(1)

Computing XOR(arr1) takes O(n) time and O(1) space. Computing XOR(arr2) takes O(m) time and O(1) space. The final AND is a single operation. No extra arrays or data structures are needed.

Compare this to the brute-force approach of iterating over all pairs, which takes O(n * m) time. For arrays of length 100,000, that is 10 billion operations. The identity brings it down to 200,000.

The building blocks

1. XOR properties: self-inverse, associative, commutative

XOR has three properties that make it extremely useful. First, a XOR a = 0 (self-inverse). Second, (a XOR b) XOR c = a XOR (b XOR c) (associative). Third, a XOR b = b XOR a (commutative). Together, these mean you can XOR elements in any order and cancel duplicates freely. The XOR of a collection counts the parity of each bit position across all values.

2. AND distributes over XOR

This is the star of the show. a AND (b XOR c) = (a AND b) XOR (a AND c). This holds because at each bit position, AND acts like multiplication (0 or 1) and XOR acts like addition mod 2. Multiplication distributes over addition in any ring, including the integers mod 2. This algebraic fact is what collapses the double loop into two single passes.

Drill bit manipulation building blocks with spaced repetition

Edge cases

Single element in each array. The answer is simply arr1[0] AND arr2[0]. XOR of a single-element array is the element itself.
All zeros. If every element in either array is 0, the XOR of that array is 0, so the AND result is 0 regardless of the other array.
All elements the same. If arr1 has n copies of value v, then XOR(arr1) is v when n is odd and 0 when n is even. The same logic applies to arr2.
Large values. The identity works for any integer size. Each bit position is independent, so 32-bit or 64-bit values are handled the same way.

From understanding to recall

The distribution law a AND (b XOR c) = (a AND b) XOR (a AND c) is the kind of identity that you either know cold or you don't. When you see a problem involving XOR of all pairwise ANDs, the identity should surface instantly. But that only happens through deliberate practice.

Spaced repetition helps you build that recall. You prove the identity from scratch today, reconstruct the bit-by-bit argument in three days, and write the one-liner solution from memory a week later. Each repetition moves the pattern from "something I figured out once" to "something I just know." The next time you encounter a problem that mixes AND and XOR, you will recognize the opportunity immediately.

Single Number - XOR fundamentals for finding unique elements
Bitwise AND of Numbers Range - Bitwise AND patterns on ranges
XOR Queries of a Subarray - Prefix XOR for efficient range queries

CodeBricks breaks problems like this into their core building blocks and drills them independently. Instead of memorizing solutions, you build fluency with the underlying techniques, so you can apply them to new problems on the spot.

Try CodeBricks free