#2425

Medium

LeetCode Problem Workspace

Bitwise XOR of All Pairings

Compute the overall bitwise XOR from all pairings between two arrays using efficient array and bit manipulation techniques.

array bit manipulation brainteaser

Problem Statement

You are given two arrays nums1 and nums2 containing non-negative integers. Define nums3 as the array containing the bitwise XOR of every pair where one element is from nums1 and one is from nums2, pairing each element exactly once with all elements from the other array.

Return the single integer representing the bitwise XOR of all elements in nums3. For example, given nums1 = [2,1,3] and nums2 = [10,2,5,0], the output should be 13 since the XOR of all pairwise XOR results equals 13.

Examples

Example 1

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

Output: 13

A possible nums3 array is [8,0,7,2,11,3,4,1,9,1,6,3]. The bitwise XOR of all these numbers is 13, so we return 13.

Example 2

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

Output: 0

All possible pairs of bitwise XORs are nums1[0] ^ nums2[0], nums1[0] ^ nums2[1], nums1[1] ^ nums2[0], and nums1[1] ^ nums2[1]. Thus, one possible nums3 array is [2,5,1,6]. 2 ^ 5 ^ 1 ^ 6 = 0, so we return 0.

Constraints

1 <= nums1.length, nums2.length <= 105
0 <= nums1[i], nums2[j] <= 109

Solution Approach

Analyze contribution of each array element

Notice that each element in nums1 will XOR with every element in nums2. If nums2 has an even length, each nums1 element appears an even number of times in XOR combinations, canceling itself. Otherwise, it contributes directly to the final XOR. Apply the same logic for nums2 elements with respect to nums1.

Compute XOR without explicit pairings

Instead of generating nums3, calculate the XOR of nums1 only if nums2 length is odd and XOR of nums2 only if nums1 length is odd. Then XOR these two results together to get the final answer. This eliminates the O(n*m) cost of enumerating all pairings.

Implement efficiently in linear time

Iterate through nums1 once to compute XOR of all elements and through nums2 once for its XOR. Conditionally include each XOR based on the opposite array length parity. Combine results to return the final XOR. This ensures O(n + m) time and O(1) extra space usage.

Complexity Analysis

Metric	Value
Time	O(n + m)
Space	O(1)

Time complexity is O(n + m) because we iterate through nums1 and nums2 once. Space complexity is O(1) since no additional arrays proportional to input sizes are created.

What Interviewers Usually Probe

Watch if candidate suggests generating all pairs; it signals they might not notice XOR parity optimization.
Check whether candidate identifies the cancellation pattern when array lengths are even.
See if candidate applies the XOR accumulation technique without extra space.

Common Pitfalls or Variants

Common pitfalls

Generating nums3 explicitly leads to TLE for large arrays.
Ignoring array length parity causes incorrect XOR results.
Applying XOR naively without considering cancellation can mislead the computation.

Follow-up variants

Compute XOR of all pairwise sums instead of XORs between two arrays.
Find the XOR of pairings where nums1 and nums2 may include negative integers.
Determine XOR across multiple arrays in a chain of pairings, testing extension of parity logic.

FAQ

What is the key trick to solve Bitwise XOR of All Pairings efficiently?

The key is noticing that elements paired an even number of times cancel out, so only elements paired an odd number of times affect the final XOR.

Do I need to build all pair combinations in nums3?

No, building nums3 is unnecessary and inefficient; just compute XORs conditionally based on opposite array length parity.

Can this method handle arrays of length up to 100,000?

Yes, because the solution runs in O(n + m) time and uses O(1) extra space, suitable for large arrays.

What happens if both arrays have even lengths?

All elements pair an even number of times, so the final XOR is zero due to cancellation.

How does array plus bit manipulation pattern apply here?

The pattern is seen in computing XOR across pairs efficiently without explicit enumeration, leveraging bitwise properties and array length parity.

terminal

Solution

Solution 1: Quick Thinking + Bit Manipulation

Since each element of the array will be XORed with each element of another array, we know that the result remains the same when the same number is XORed twice, i.e., $a \oplus a = 0$. Therefore, we only need to count the length of the array to know how many times each element is XORed with each element of another array.

1

2

3

4

5

6

7

8

9

10

class Solution:
    def xorAllNums(self, nums1: List[int], nums2: List[int]) -> int:
        ans = 0
        if len(nums2) & 1:
            for v in nums1:
                ans ^= v
        if len(nums1) & 1:
            for v in nums2:
                ans ^= v
        return ans

Continue Practicing

#2419 longest subarray with maximum bitwise and #2568 minimum impossible or #2433 find the original array of prefix xor