LeetCode 2425 - Bitwise XOR of All Pairings

The problem gives us two arrays, nums1 and nums2, and asks us to compute the XOR of every possible pair formed between the two arrays. For every element in nums1, we pair it with every element in nums2 exactly once.

leetcodemediumarraybit-manipulationbrainteaser

LeetCode Problem 2425

Difficulty: 🟡 Medium
Topics: Array, Bit Manipulation, Brainteaser

Solution

Problem Understanding

The problem gives us two arrays, nums1 and nums2, and asks us to compute the XOR of every possible pair formed between the two arrays.

For every element in nums1, we pair it with every element in nums2 exactly once. Each pair produces a value using the bitwise XOR operation:

nums1[i] ^ nums2[j]

If nums1 has length m and nums2 has length n, then there are m × n pairings in total. These pairwise XOR values conceptually form another array, nums3, and the task is to return the XOR of all values inside nums3.

In other words, we want:

(nums1[0] ^ nums2[0]) ^
(nums1[0] ^ nums2[1]) ^
...
(nums1[m-1] ^ nums2[n-1])

A naive interpretation suggests explicitly generating every pairing, but the constraints immediately indicate that this approach will not scale.

The array lengths can each be as large as 10^5. That means the total number of pairings could be:

10^5 × 10^5 = 10^10

Processing ten billion pairs is computationally infeasible within normal time limits. This strongly suggests there is a mathematical observation or XOR property that lets us avoid enumerating all pairings.

The values themselves are non-negative integers up to 10^9, which means normal integer operations are sufficient and there are no concerns about overflow in Python or standard integer handling in Go.

An important observation is that XOR has useful cancellation properties:

x ^ x = 0
x ^ 0 = x

This means values appearing an even number of times cancel out completely. Since every number from one array participates in many pairings, frequency matters more than explicit construction.

Edge cases worth identifying early include:

  • When one array has length 1, because every element of the other array contributes exactly once.
  • When one or both arrays have even lengths, since XOR cancellation becomes important.
  • Arrays containing 0, because XOR with zero leaves values unchanged.
  • Large arrays where brute force becomes impossible, reinforcing the need for an optimized mathematical approach.

Approaches

Brute Force

The brute-force solution directly simulates the problem statement.

For every element in nums1, iterate through every element in nums2, compute the XOR for that pair, and continuously XOR the result into an accumulator.

Conceptually:

answer ^= (nums1[i] ^ nums2[j])

This works because it exactly reproduces the definition of nums3. Every pair is generated once, and every generated value contributes to the final XOR.

However, the time complexity is prohibitively expensive. Since every element in nums1 is paired with every element in nums2, the runtime becomes O(m × n). With both arrays reaching 10^5, this becomes 10^10 operations, which is far too slow.

Optimal Approach, XOR Contribution Observation

The key insight comes from understanding how often each number contributes to the final XOR.

Suppose an element x appears in nums1.

Since x pairs with every element in nums2, it appears in XOR operations exactly:

len(nums2)

times.

If len(nums2) is even, then:

x ^ x ^ x ^ x ... (even times) = 0

So every contribution from x cancels out.

If len(nums2) is odd, then:

x ^ x ^ x ... (odd times) = x

So x survives exactly once.

The same logic applies symmetrically to elements in nums2.

Therefore:

  • If len(nums2) is odd, XOR all elements of nums1 into the answer.
  • If len(nums1) is odd, XOR all elements of nums2 into the answer.

This reduces the problem from checking all pairings to simply XORing array elements based on parity.

Approach Time Complexity Space Complexity Notes
Brute Force O(m × n) O(1) Explicitly computes every pairwise XOR
Optimal O(m + n) O(1) Uses XOR cancellation and parity of array lengths

Algorithm Walkthrough

  1. Initialize a variable result to 0.

This variable stores the running XOR answer. Since XOR with 0 leaves a value unchanged, 0 is the natural starting point. 2. Check whether the length of nums2 is odd.

If len(nums2) is odd, every number in nums1 contributes an odd number of times to the total XOR, meaning those contributions survive.

Iterate through nums1 and XOR every element into result. 3. Check whether the length of nums1 is odd.

If len(nums1) is odd, every number in nums2 contributes an odd number of times.

Iterate through nums2 and XOR every element into result. 4. Return result.

By this point, all elements that survive cancellation have been included exactly once.

Why it works

The correctness relies on the cancellation property of XOR.

Every element in nums1 appears exactly len(nums2) times in all pairings. If that count is even, all copies cancel out. If it is odd, one copy remains. The same logic applies to nums2.

Since XOR is associative and commutative, we can regroup all pair contributions by element frequency rather than computing individual pairs. This guarantees that the algorithm produces the same final XOR as explicitly generating nums3.

Python Solution

from typing import List

class Solution:
    def xorAllNums(self, nums1: List[int], nums2: List[int]) -> int:
        result = 0

        if len(nums2) % 2 == 1:
            for num in nums1:
                result ^= num

        if len(nums1) % 2 == 1:
            for num in nums2:
                result ^= num

        return result

The implementation follows the mathematical observation directly.

We start with result = 0, which acts as the XOR accumulator.

The first conditional checks whether nums2 has odd length. If it does, every element in nums1 contributes an odd number of times to the final answer, so we XOR all values from nums1 into result.

The second conditional mirrors this logic. If nums1 has odd length, every element in nums2 survives cancellation, so we XOR all values from nums2.

Finally, the computed XOR is returned.

Notice that no pairings are explicitly constructed. Instead, the implementation leverages contribution counting through parity, which makes it efficient enough for the problem constraints.

Go Solution

func xorAllNums(nums1 []int, nums2 []int) int {
	result := 0

	if len(nums2)%2 == 1 {
		for _, num := range nums1 {
			result ^= num
		}
	}

	if len(nums1)%2 == 1 {
		for _, num := range nums2 {
			result ^= num
		}
	}

	return result
}

The Go implementation is nearly identical to the Python version.

Go slices naturally support iteration using range, which makes XOR accumulation concise and readable.

There are no special concerns regarding integer overflow because the problem constraints fit comfortably within Go's integer range. Nil slices are also handled naturally, although the problem guarantees non-empty arrays.

Worked Examples

Example 1

Input:

nums1 = [2,1,3]
nums2 = [10,2,5,0]

First, determine array lengths:

len(nums1) = 3 (odd)
len(nums2) = 4 (even)

Since nums2 has even length, contributions from nums1 cancel out.

Since nums1 has odd length, elements in nums2 survive.

Step Action Result
Start Initialize 0
XOR 10 0 ^ 10 10
XOR 2 10 ^ 2 8
XOR 5 8 ^ 5 13
XOR 0 13 ^ 0 13

Final answer:

13

Example 2

Input:

nums1 = [1,2]
nums2 = [3,4]

Lengths:

len(nums1) = 2 (even)
len(nums2) = 2 (even)

Since both lengths are even:

  • nums1 contributions cancel out.
  • nums2 contributions cancel out.
Step Action Result
Start Initialize 0
No contribution from nums1 Even repetition count 0
No contribution from nums2 Even repetition count 0

Final answer:

0

Complexity Analysis

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

The algorithm performs at most one pass through each array. Since no nested loops are used, the total runtime is linear in the combined size of the inputs.

Memory usage stays constant because we only maintain an accumulator variable and loop variables. No additional data structures are allocated.

Test Cases

solution = Solution()

# Provided examples
assert solution.xorAllNums([2, 1, 3], [10, 2, 5, 0]) == 13  # Example 1
assert solution.xorAllNums([1, 2], [3, 4]) == 0  # Example 2

# Single-element arrays
assert solution.xorAllNums([5], [7]) == 2  # 5 ^ 7

# One odd length, one even length
assert solution.xorAllNums([1, 2, 3], [4, 5]) == 1 ^ 2 ^ 3  # nums1 survives
assert solution.xorAllNums([1, 2], [4, 5, 6]) == 4 ^ 5 ^ 6  # nums2 survives

# Both odd lengths
assert solution.xorAllNums([1, 2, 3], [4, 5, 6]) == (
    (1 ^ 2 ^ 3) ^ (4 ^ 5 ^ 6)
)  # both contribute

# Both even lengths
assert solution.xorAllNums([8, 9], [10, 11]) == 0  # everything cancels

# Arrays containing zero
assert solution.xorAllNums([0, 1], [0, 2, 3]) == (
    0 ^ 2 ^ 3
)  # zero handling

# Large repeated values
assert solution.xorAllNums([1000000000], [1000000000]) == 0  # max values

# Repeated numbers
assert solution.xorAllNums([7, 7, 7], [1]) == 7  # XOR repetition
Test Why
[2,1,3], [10,2,5,0] Validates the first official example
[1,2], [3,4] Validates the second official example
[5], [7] Smallest valid input size
Odd/even combinations Verifies parity logic
Both odd lengths Ensures both arrays contribute
Both even lengths Confirms total cancellation
Arrays containing 0 Tests XOR identity behavior
Large values Confirms handling near constraint maximum
Repeated values Validates XOR cancellation behavior

Edge Cases

Both Arrays Have Even Length

This is a common source of mistakes because every element appears an even number of times.

For example:

nums1 = [1,2]
nums2 = [3,4]

Every contribution cancels completely, producing 0. A buggy implementation might incorrectly XOR the arrays regardless of parity. The implementation avoids this by only processing an array when the opposite array has odd length.

Single-Element Arrays

When both arrays contain one element, there is only one pairing.

Example:

nums1 = [5]
nums2 = [7]

The answer is simply:

5 ^ 7 = 2

Since both lengths are odd, the algorithm correctly XORs both arrays into the result.

Arrays Containing Zero

Zero behaves specially in XOR operations:

x ^ 0 = x

A careless implementation might accidentally treat zero as a special case unnecessarily. The current solution requires no extra handling because XOR naturally supports it.

For example:

nums1 = [0,1]
nums2 = [0,2,3]

Only nums2 contributes because nums1 has even length, and XOR with 0 leaves the result unchanged.