Find XOR Sum of All Pairs Bitwise AND - Solution & Explanation

Q: Is Find XOR Sum of All Pairs Bitwise AND easy or hard?

The problem is classified as Hard on LeetCode because recognizing the XOR distribution property is not obvious. Once the mathematical insight is known, the implementation becomes short and runs in linear time.

Q: Find XOR Sum of All Pairs Bitwise AND Python/Java solution

The typical implementation computes two XOR aggregates using a loop over each array, then returns their bitwise AND. This logic translates directly across Python, Java, C++, JavaScript, and other languages because the operators ^ (XOR) and & (AND) behave consistently.

Q: How to solve Find XOR Sum of All Pairs Bitwise AND in O(n)?

Compute xor1 as the XOR of all elements in arr1 and xor2 as the XOR of all elements in arr2. The final answer is xor1 & xor2. Each array is scanned once, so the total complexity is O(n + m) with constant extra space.

Q: What is the best approach for Find XOR Sum of All Pairs Bitwise AND?

The optimal approach uses a bitwise XOR theorem. Compute the XOR of all elements in arr1 and the XOR of all elements in arr2, then take the bitwise AND of those two results. This works because AND distributes over XOR across pair combinations. The algorithm runs in O(n + m) time and O(1) space.

Q: Is Find XOR Sum of All Pairs Bitwise AND asked at Google/Amazon/Meta?

Problems involving XOR identities and bit manipulation frequently appear in interviews at companies like Google, Amazon, and Meta. Variants often test whether candidates recognize algebraic properties that reduce pairwise computations.

Q: What data structure is used in Find XOR Sum of All Pairs Bitwise AND?

No special data structure is required. The solution relies on array traversal and bit manipulation operations such as XOR and AND. The optimized approach maintains only two running XOR values.

Q: What is the time complexity of Find XOR Sum of All Pairs Bitwise AND?

The brute force method takes O(n*m) time because every element of arr1 is paired with every element of arr2. The optimized approach reduces the complexity to O(n + m) by computing two cumulative XOR values and applying a single AND operation.

HardArray Math Bit Manipulation17 min readAsked at: Mobisy

Practice this problem

Problem Statement

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.

For example, the XOR sum of [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 <= 10⁵
0 <= arr1[i], arr2[j] <= 10⁹

Approach Overview

Problem 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 1: Bitwise XOR Theorem

According to a known result in bitwise operations, the XOR sum of all elements generated from AND operation of two lists can be significantly reduced. If you calculate the XOR of each element of the first list, and then perform the same for the second list, taking the AND of the two results will give the answer. This heavily reduces the number of computations needed compared to finding the AND for every possible pair.

The function findXORSum computes the XOR of all elements in arr1 and arr2 separately, then computes the AND of these two XOR results. This approach leverages the properties of XOR and AND to minimize computations.

Code

C C++Java Python C#JavaScript

C++

Java

Python

JavaScript

Complexity

Time Complexity: O(n + m), where n is the length of arr1 and m is the length of arr2.
Space Complexity: O(1), only a few variables are used.

Try this approach in the editor →

Approach 2: Brute Force Approach

This approach considers every possible pair of elements from arr1 and arr2, computes the AND for each pair, and then XORs all the resulting ANDed values. It is straightforward but computationally expensive due to its direct implementation of the problem statement.

This brute force solution simply iterates over every i-th element in arr1 and every j-th element in arr2, calculating the AND and using it to update the overall XOR result.

Code

C C++Java Python C#JavaScript

C++

Java

Python

JavaScript

Complexity

Time Complexity: O(n*m), where n is the length of arr1 and m is the length of arr2.
Space Complexity: O(1), no additional data structures used beyond a counter.

Try this approach in the editor →

Approach 3: 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:

$\begin{aligned} ans &= (a_1 \wedge b_1) \oplus (a_1 \wedge b_2) ... (a_1 \wedge b_m) \ &\quad \oplus (a_2 \wedge b_1) \oplus (a_2 \wedge b_2) ... (a_2 \wedge b_m) \ &\quad \oplus cdots \ &\quad \oplus (a_n \wedge b_1) \oplus (a_n \wedge b_2) ... (a_n \wedge b_m) \ \end{aligned}


Since in Boolean algebra, the XOR operation is addition without carry, and the AND operation is multiplication, the above formula can be simplified as:

ans = (a_1 \oplus a_2 \oplus cdots \oplus a_n) \wedge (b_1 \oplus b_2 \oplus cdots \oplus b_m)

That is, the bitwise AND of the XOR sum of array arr1 and the XOR sum of array arr2.

The time complexity is O(n + m), where n and m are the lengths of arrays arr1 and arr2, respectively. The space complexity is O(1)$.

Code

Python Java C++Go TypeScript

Python

Java

C++

TypeScript

Try this approach in the editor →

Complexity Comparison

Approach	Complexity
Bitwise XOR Theorem	Time Complexity: O(n + m), where n is the length of arr1 and m is the length of arr2. Space Complexity: O(1), only a few variables are used.
Brute Force Approach	Time Complexity: O(n*m), where n is the length of arr1 and m is the length of arr2. Space Complexity: O(1), no additional data structures used beyond a counter.
Bitwise Operation	—

Detailed Complexity Analysis

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

Video Solution

LeetCode 1835. Find XOR Sum of All Pairs Bitwise AND • Happy Coding • 1,369 views views

Watch 9 more video solutions →

Frequently Asked Questions

Is Find XOR Sum of All Pairs Bitwise AND easy or hard?

The problem is classified as Hard on LeetCode because recognizing the XOR distribution property is not obvious. Once the mathematical insight is known, the implementation becomes short and runs in linear time.

Find XOR Sum of All Pairs Bitwise AND Python/Java solution

The typical implementation computes two XOR aggregates using a loop over each array, then returns their bitwise AND. This logic translates directly across Python, Java, C++, JavaScript, and other languages because the operators ^ (XOR) and & (AND) behave consistently.

How to solve Find XOR Sum of All Pairs Bitwise AND in O(n)?

Compute xor1 as the XOR of all elements in arr1 and xor2 as the XOR of all elements in arr2. The final answer is xor1 & xor2. Each array is scanned once, so the total complexity is O(n + m) with constant extra space.

What is the best approach for Find XOR Sum of All Pairs Bitwise AND?

The optimal approach uses a bitwise XOR theorem. Compute the XOR of all elements in arr1 and the XOR of all elements in arr2, then take the bitwise AND of those two results. This works because AND distributes over XOR across pair combinations. The algorithm runs in O(n + m) time and O(1) space.

Is Find XOR Sum of All Pairs Bitwise AND asked at Google/Amazon/Meta?

Problems involving XOR identities and bit manipulation frequently appear in interviews at companies like Google, Amazon, and Meta. Variants often test whether candidates recognize algebraic properties that reduce pairwise computations.

What data structure is used in Find XOR Sum of All Pairs Bitwise AND?

No special data structure is required. The solution relies on array traversal and bit manipulation operations such as XOR and AND. The optimized approach maintains only two running XOR values.

What is the time complexity of Find XOR Sum of All Pairs Bitwise AND?

The brute force method takes O(n*m) time because every element of arr1 is paired with every element of arr2. The optimized approach reduces the complexity to O(n + m) by computing two cumulative XOR values and applying a single AND operation.

Ready to solve this problem?

Practice Find XOR Sum of All Pairs Bitwise AND with our built-in code editor and test cases.

Practice on FleetCode

Two Sum

Median of Two Sorted Arrays

Problem Info

DifficultyHard

Acceptance62.6%

Approaches3

Reading time17 min

Asked at

Mobisy

Practice this problem

Open in Editor

Problem Statement

Approach Overview

Approach 1: Bitwise XOR Theorem

Code

Complexity

Approach 2: Brute Force Approach

Code

Complexity

Approach 3: Bitwise Operation

Code

Complexity Comparison

Detailed Complexity Analysis

Video Solution

Frequently Asked Questions

Related Problems

Ready to solve this problem?

Problem Info

Table of Contents