1835. Find XOR Sum of All Pairs Bitwise AND Solution

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.

The problem

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.

Python

def find_xor_sum(arr1, arr2):
    xor1 = 0
    xor2 = 0
    for num in arr1:
        xor1 ^= num
    for num in arr2:
        xor2 ^= num
    return xor1 & xor2

arr1 = [1, 2, 3]
arr2 = [6, 5]
print(find_xor_sum(arr1, arr2))

Java

import java.util.*;

public class Main {
    public static int findXORSum(int[] arr1, int[] arr2) {
        int xor1 = 0, xor2 = 0;
        for (int num : arr1) {
            xor1 ^= num;
        }
        for (int num : arr2) {
            xor2 ^= num;
        }
        return xor1 & xor2;
    }

    public static void main(String[] args) {
        int[] arr1 = {1, 2, 3};
        int[] arr2 = {6, 5};
        System.out.println(findXORSum(arr1, arr2));
    }
}

C++

#include <iostream>
#include <vector>

int findXORSum(const std::vector<int>& arr1, const std::vector<int>& arr2) {
    int xor1 = 0, xor2 = 0;
    for (int num : arr1) {
        xor1 ^= num;
    }
    for (int num : arr2) {
        xor2 ^= num;
    }
    return xor1 & xor2;
}

int main() {
    std::vector<int> arr1 = {1, 2, 3};
    std::vector<int> arr2 = {6, 5};
    std::cout << findXORSum(arr1, arr2) << std::endl;
    return 0;
}

JavaScript

function findXorSum(arr1, arr2) {
    let xor1 = 0, xor2 = 0;
    for (let num of arr1) {
        xor1 ^= num;
    }
    for (let num of arr2) {
        xor2 ^= num;
    }
    return xor1 & xor2;
}

const arr1 = [1, 2, 3];
const arr2 = [6, 5];
console.log(findXorSum(arr1, arr2));

#include <stdio.h>

int findXORSum(int* arr1, int size1, int* arr2, int size2) {
    int xor1 = 0, xor2 = 0;
    for (int i = 0; i < size1; i++) {
        xor1 ^= arr1[i];
    }
    for (int j = 0; j < size2; j++) {
        xor2 ^= arr2[j];
    }
    return xor1 & xor2;
}

int main() {
    int arr1[] = {1, 2, 3};
    int arr2[] = {6, 5};
    int size1 = sizeof(arr1) / sizeof(arr1[0]);
    int size2 = sizeof(arr2) / sizeof(arr2[0]);
    printf("%d\n", findXORSum(arr1, size1, arr2, size2));
    return 0;
}

using System;

public class Program {
    public static int FindXorSum(int[] arr1, int[] arr2) {
        int xor1 = 0, xor2 = 0;
        foreach (int num in arr1) {
            xor1 ^= num;
        }
        foreach (int num in arr2) {
            xor2 ^= num;
        }
        return xor1 & xor2;
    }

    public static void Main() {
        int[] arr1 = { 1, 2, 3 };
        int[] arr2 = { 6, 5 };
        Console.WriteLine(FindXorSum(arr1, arr2));
    }
}

The Python solution employs simple iteration using built-in loops and the XOR operation with the caret ^ operator, similar to the concepts illustrated in other language solutions.

Complexity

Time Complexity: O(n+m), where n is the size of arr1 and m is the size of arr2.
Space Complexity: O(1), using constant space.

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.

Python

def find_xor_sum_brute_force(arr1, arr2):
    result = 0
    for num1 in arr1:
        for num2 in arr2:
            result ^= num1 & num2
    return result

arr1 = [1, 2, 3]
arr2 = [6, 5]
print(find_xor_sum_brute_force(arr1, arr2))

Java

import java.util.*;

public class Main {
    public static int findXORSumBruteForce(int[] arr1, int[] arr2) {
        int result = 0;
        for (int num1 : arr1) {
            for (int num2 : arr2) {
                result ^= (num1 & num2);
            }
        }
        return result;
    }

    public static void main(String[] args) {
        int[] arr1 = {1, 2, 3};
        int[] arr2 = {6, 5};
        System.out.println(findXORSumBruteForce(arr1, arr2));
    }
}

C++

#include <iostream>
#include <vector>

int findXORSumBruteForce(const std::vector<int>& arr1, const std::vector<int>& arr2) {
    int result = 0;
    for (int num1 : arr1) {
        for (int num2 : arr2) {
            result ^= (num1 & num2);
        }
    }
    return result;
}

int main() {
    std::vector<int> arr1 = {1, 2, 3};
    std::vector<int> arr2 = {6, 5};
    std::cout << findXORSumBruteForce(arr1, arr2) << std::endl;
    return 0;
}

JavaScript

function findXorSumBruteForce(arr1, arr2) {
    let result = 0;
    for (let num1 of arr1) {
        for (let num2 of arr2) {
            result ^= num1 & num2;
        }
    }
    return result;
}

const arr1 = [1, 2, 3];
const arr2 = [6, 5];
console.log(findXorSumBruteForce(arr1, arr2));

#include <stdio.h>

int findXORSumBruteForce(int* arr1, int size1, int* arr2, int size2) {
    int result = 0;
    for (int i = 0; i < size1; i++) {
        for (int j = 0; j < size2; j++) {
            result ^= (arr1[i] & arr2[j]);
        }
    }
    return result;
}

int main() {
    int arr1[] = {1, 2, 3};
    int arr2[] = {6, 5};
    int size1 = sizeof(arr1) / sizeof(arr1[0]);
    int size2 = sizeof(arr2) / sizeof(arr2[0]);
    printf("%d\n", findXORSumBruteForce(arr1, size1, arr2, size2));
    return 0;
}

using System;

public class Program {
    public static int FindXorSumBruteForce(int[] arr1, int[] arr2) {
        int result = 0;
        foreach (int num1 in arr1) {
            foreach (int num2 in arr2) {
                result ^= (num1 & num2);
            }
        }
        return result;
    }

    public static void Main() {
        int[] arr1 = { 1, 2, 3 };
        int[] arr2 = { 6, 5 };
        Console.WriteLine(FindXorSumBruteForce(arr1, arr2));
    }
}

The Python code simply iterates over both lists with nested loops, computing AND for each pair and updating the overall XOR tally.

Complexity

Time Complexity: O(n*m), as you are processing each element in the nested iteration.
Space Complexity: O(1), uses a few extra placeholders here.

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)$.

TypeScript

function getXORSum(arr1: number[], arr2: number[]): number {
    const a = arr1.reduce((acc, x) => acc ^ x);
    const b = arr2.reduce((acc, x) => acc ^ x);
    return a & b;
}

func getXORSum(arr1 []int, arr2 []int) int {
	var a, b int
	for _, v := range arr1 {
		a ^= v
	}
	for _, v := range arr2 {
		b ^= v
	}
	return a & b
}

Try this approach in the editor

Complexity comparison

Approach	Complexity
Bitwise XOR Theorem	Time Complexity: O(n+m), where n is the size of arr1 and m is the size of arr2. Space Complexity: O(1), using constant space.
Brute Force Approach	Time Complexity: O(n*m), as you are processing each element in the nested iteration. Space Complexity: O(1), uses a few extra placeholders here.
Bitwise Operation	–

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

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.

Find XOR Sum of All Pairs Bitwise AND solution and explanation

The problem

Approach overview

Approach 1: Bitwise XOR Theorem

Approach 2: Brute Force Approach

Approach 3: Bitwise Operation

Complexity comparison

Complexity analysis

Frequently asked questions

Comments

Find XOR Sum of All Pairs Bitwise AND solution and explanation

The problem

Approach overview

Approach 1: Bitwise XOR Theorem

Approach 2: Brute Force Approach

Approach 3: Bitwise Operation

Complexity comparison

Complexity analysis

Frequently asked questions

Comments

Related problems