#1835

Hard

LeetCode Problem Workspace

Find XOR Sum of All Pairs Bitwise AND

Compute the XOR sum of all pairwise ANDs between two integer arrays using array and bitwise math techniques efficiently.

array math bit manipulation

Problem Statement

You are given two non-empty 0-indexed arrays arr1 and arr2 consisting of non-negative integers. Define a new list containing the result of arr1[i] AND arr2[j] for every pair of indices i and j where 0 <= i < arr1.length and 0 <= j < arr2.length. Your task is to compute the XOR sum of all values in this list.

The XOR sum of a list is obtained by performing a bitwise XOR operation on all its elements. For example, if the list contains only one element, its XOR sum is that element itself. Optimize the computation to handle large arrays efficiently, focusing on bit manipulation and the array plus math pattern rather than computing every pair explicitly.

Examples

Example 1

Input: arr1 = [1,2,3], arr2 = [6,5]

Output: 0

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

The list = [12 AND 4] = [4]. The XOR sum = 4.

Constraints

1 <= arr1.length, arr2.length <= 105
0 <= arr1[i], arr2[j] <= 109

Solution Approach

Analyze Each Bit Separately

Break down the XOR sum problem by considering each bit position independently. Count the number of elements in arr1 and arr2 that have the current bit set. If the product of these counts is odd, this bit contributes 1 to the final XOR sum; otherwise it contributes 0.

Use Bitwise Patterns

Leverage the identity (a&b) XOR (a&c) = a & (b XOR c) to simplify computation across arrays. This allows reduction from O(n*m) naive pair evaluation to a linear pass for each bit, maintaining efficiency for large arrays.

Compute XOR Sum Efficiently

Iterate over all bit positions up to 30 since numbers are <= 10^9. For each bit, determine contribution to the XOR sum and accumulate the result. This avoids generating all pairwise AND results while directly computing the final XOR.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

Time complexity is O(max_bit * (len(arr1) + len(arr2))) since each bit is evaluated across both arrays. Space complexity is O(1) additional memory beyond input arrays because we only track counts per bit.

What Interviewers Usually Probe

Expect recognition of bitwise simplification and avoidance of naive pair enumeration.
Check for independent bit analysis using counts instead of generating full AND matrix.
Listen for insight using (a&b) XOR (a&c) identity to optimize computation.

Common Pitfalls or Variants

Common pitfalls

Attempting to compute all pairwise ANDs explicitly leads to TLE for large arrays.
Overlooking bit positions beyond 30 can cause incorrect XOR sums for large numbers.
Failing to correctly multiply counts of set bits from both arrays may yield wrong results.

Follow-up variants

Compute XOR sum of all pairs using OR instead of AND.
Find XOR sum of all triplet ANDs across three arrays.
Calculate XOR sum of all pairwise ANDs but only for even indexed elements.

FAQ

What does 'Find XOR Sum of All Pairs Bitwise AND' mean?

It means calculating the XOR of every result obtained by ANDing each element from arr1 with each element from arr2 without generating all pairs explicitly.

Can this problem be solved without nested loops over both arrays?

Yes, by analyzing each bit independently and counting contributions from both arrays, the XOR sum can be computed in linear time per bit.

Why is (a&b) XOR (a&c) = a & (b XOR c) useful here?

This identity allows simplification across array elements, reducing computation from quadratic to linear per bit, which is critical for large arrays.

What are common mistakes when implementing this problem?

Naively computing all pairwise ANDs, ignoring higher bits, or miscounting set bits can all lead to wrong results or timeouts.

Does the solution handle very large arrays efficiently?

Yes, by iterating bit by bit and using counts, it avoids O(n*m) complexity and uses minimal extra space.

terminal

Solution

Solution 1: Bitwise Operation

Assume that the elements of array $arr1$ are $a_1, a_2, ..., a_n$, and the elements of array $arr2$ are $b_1, b_2, ..., b_m$. Then, the answer to the problem is:

1

2

3

4

5

class Solution:
    def getXORSum(self, arr1: List[int], arr2: List[int]) -> int:
        a = reduce(xor, arr1)
        b = reduce(xor, arr2)
        return a & b

Continue Practicing

#1863 sum of all subset xor totals #1799 maximize score after n operations #1994 the number of good subsets