LeetCode Problem 1835

Difficulty: 🔴 Hard
Topics: Array, Math, Bit Manipulation

Solution

LeetCode 1835 - Find XOR Sum of All Pairs Bitwise AND

Problem Understanding

This problem asks us to compute the XOR sum of every possible pairwise bitwise AND between two arrays.

More formally, for every pair (i, j):

• Take arr1[i] AND arr2[j]
• Add that result to a conceptual list
• Compute the XOR of all values in that list

The challenge is that both arrays can contain up to 10^5 elements. A naive approach that explicitly generates all pairwise AND values would require up to:

$$10^5 \times 10^5 = 10^{10}$$

operations, which is completely infeasible.

The key part of the problem is recognizing that bitwise operations have algebraic properties that let us simplify the expression dramatically.

The input arrays contain non-negative integers, and all values fit comfortably within standard 32-bit integer ranges since each value is at most 10^9.

The output is a single integer representing the XOR sum of all pairwise AND values.

One important detail is that XOR is associative and commutative. This means order does not matter, and repeated values can cancel out. Specifically:

$$x \oplus x = 0$$

This cancellation behavior is the core observation behind the optimal solution.

Another important edge case is when arrays contain only one element. In that situation, the answer is simply the AND of those two values. The problem also guarantees that both arrays contain at least one element, so we never need to handle empty arrays.

Approaches

Brute Force Approach

The most direct solution is to iterate through every pair (i, j) and compute:

$$arr1[i] & arr2[j]$$

We maintain a running XOR of all these values.

This works because it exactly follows the problem definition. Every possible pairwise AND is generated and included in the final XOR sum.

However, the time complexity is extremely large. If both arrays contain 10^5 elements, we would need:

$$10^{10}$$

pair operations.

That is far beyond acceptable limits for a coding interview or competitive programming environment.

Optimal Bitwise Observation

The critical insight is the following identity:

$$(a_1 \oplus a_2 \oplus \dots \oplus a_n) & (b_1 \oplus b_2 \oplus \dots \oplus b_m)$$

is equal to:

$$(a_1 & b_1) \oplus (a_1 & b_2) \oplus \dots \oplus (a_n & b_m)$$

In simpler terms:

$$\text{XOR of all pairwise ANDs} = (\text{XOR of arr1}) & (\text{XOR of arr2})$$

This works because bitwise AND distributes over XOR at the bit level.

Instead of computing every pair, we can:

1. XOR all elements in arr1
2. XOR all elements in arr2
3. AND the two XOR results

This reduces the complexity from quadratic to linear.

Approach Comparison

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n × m)	O(1)	Computes every pairwise AND explicitly
Optimal	O(n + m)	O(1)	Uses XOR and AND distributive properties

Algorithm Walkthrough

1. Initialize a variable xor1 to 0.
2. Traverse arr1. For each value, XOR it into xor1.

This computes:

$$xor1 = arr1[0] \oplus arr1[1] \oplus \dots$$ 3. Initialize another variable xor2 to 0. 4. Traverse arr2. For each value, XOR it into xor2.

This computes:

$$xor2 = arr2[0] \oplus arr2[1] \oplus \dots$$ 5. Return:

$$xor1 & xor2$$ 6. The distributive property guarantees that this result equals the XOR of all pairwise AND values.

Why it works

Bitwise operations can be analyzed independently for each bit position.

A bit contributes to the final XOR sum only if it appears an odd number of times among all pairwise AND results.

For a particular bit to survive in a pairwise AND:

• That bit must be set in some element from arr1
• That bit must also be set in some element from arr2

The parity behavior of XOR means we only care whether the count of occurrences is odd or even.

Computing XOR across each array independently captures exactly that parity information. Taking the AND of those two XOR values reconstructs the final answer.

Python Solution

from typing import List

class Solution:
    def getXORSum(self, arr1: List[int], arr2: List[int]) -> int:
        xor_arr1 = 0
        xor_arr2 = 0

        for value in arr1:
            xor_arr1 ^= value

        for value in arr2:
            xor_arr2 ^= value

        return xor_arr1 & xor_arr2

The implementation follows the mathematical identity directly.

The variable xor_arr1 stores the cumulative XOR of all elements in the first array. XOR accumulation works efficiently because XOR is associative and commutative.

The second loop computes the XOR of all elements in arr2.

Finally, we return the bitwise AND of the two XOR aggregates.

The implementation uses only constant extra memory and processes each element exactly once.

Go Solution

func getXORSum(arr1 []int, arr2 []int) int {
	xorArr1 := 0
	xorArr2 := 0

	for _, value := range arr1 {
		xorArr1 ^= value
	}

	for _, value := range arr2 {
		xorArr2 ^= value
	}

	return xorArr1 & xorArr2
}

The Go implementation is almost identical to the Python version.

Go uses the ^= operator for XOR assignment and & for bitwise AND. Since all values fit within standard integer ranges, there are no overflow concerns.

Slices in Go behave similarly to dynamic arrays, and iteration is handled cleanly using the range keyword.

Worked Examples

Example 1

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

Step 1: XOR all values in arr1

Operation	Result
0 XOR 1	1
1 XOR 2	3
3 XOR 3	0

So:

$$xorArr1 = 0$$

Step 2: XOR all values in arr2

Operation	Result
0 XOR 6	6
6 XOR 5	3

So:

$$xorArr2 = 3$$

Step 3: AND the two XOR results

$$0 & 3 = 0$$

Final answer:

0

Verification Using Brute Force

Pair	AND Result
1 & 6	0
1 & 5	1
2 & 6	2
2 & 5	0
3 & 6	2
3 & 5	1

XOR all values:

$$0 \oplus 1 \oplus 2 \oplus 0 \oplus 2 \oplus 1 = 0$$

The result matches.

Example 2

arr1 = [12]
arr2 = [4]

Step 1: XOR arr1

$$xorArr1 = 12$$

Step 2: XOR arr2

$$xorArr2 = 4$$

Step 3: AND the results

$$12 & 4 = 4$$

Final answer:

4

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n + m)	Each array is traversed once
Space	O(1)	Only a few integer variables are used

The algorithm is extremely efficient because it avoids generating pairwise combinations entirely.

Instead of processing n × m AND operations, it processes each element exactly once and uses algebraic properties of XOR and AND to derive the final answer directly.

Test Cases

from typing import List

class Solution:
    def getXORSum(self, arr1: List[int], arr2: List[int]) -> int:
        xor_arr1 = 0
        xor_arr2 = 0

        for value in arr1:
            xor_arr1 ^= value

        for value in arr2:
            xor_arr2 ^= value

        return xor_arr1 & xor_arr2

solution = Solution()

assert solution.getXORSum([1,2,3], [6,5]) == 0  # provided example 1
assert solution.getXORSum([12], [4]) == 4  # provided example 2

assert solution.getXORSum([0], [0]) == 0  # both arrays contain zero
assert solution.getXORSum([7], [7]) == 7  # single identical values
assert solution.getXORSum([1,1], [1,1]) == 0  # XOR cancellation behavior
assert solution.getXORSum([5,5,5], [3]) == 1  # repeated values with odd count
assert solution.getXORSum([8,1,2], [4,2]) == ((8 ^ 1 ^ 2) & (4 ^ 2))  # mixed bits
assert solution.getXORSum([1024,2048], [4096,8192]) == 0  # no overlapping bits
assert solution.getXORSum([15,7,3], [1,2,4]) == ((15 ^ 7 ^ 3) & (1 ^ 2 ^ 4))  # multiple bit patterns
assert solution.getXORSum([10**9], [10**9]) == 10**9  # large values

Test Case Summary

Test	Why
[1,2,3], [6,5]	Validates provided example
[12], [4]	Tests single-element arrays
[0], [0]	Ensures zero handling works
[7], [7]	Tests direct AND result
[1,1], [1,1]	Verifies XOR cancellation
[5,5,5], [3]	Tests odd repetition counts
[8,1,2], [4,2]	Tests mixed bit positions
[1024,2048], [4096,8192]	Tests non-overlapping bits
[15,7,3], [1,2,4]	Tests varied binary combinations
[10^9], [10^9]	Confirms large integer handling

Edge Cases

One important edge case occurs when both arrays contain only zeros. Since XOR of zeros remains zero and AND with zero is also zero, the algorithm naturally returns the correct answer without any special handling.

Another important case involves repeated values. XOR has cancellation behavior, where identical values appearing an even number of times disappear entirely. A naive understanding of the problem might overlook this property and incorrectly assume duplicates always contribute to the result. The XOR accumulation step correctly handles these cancellations automatically.

A third important edge case occurs when the arrays contain values with completely disjoint bit patterns. For example, powers of two with no overlapping set bits produce a final AND result of zero. The algorithm correctly captures this because the final AND operation preserves only bits present in both XOR aggregates.

Finally, very large input sizes are a major concern. A brute-force solution would time out because it requires quadratic work. The optimal solution processes each array once, making it efficient even at the maximum constraints of 10^5 elements per array.