Bitwise XOR of All Pairings

Bitwise XOR of All Pairings

What is this problem about?

You are given two arrays, nums1 and nums2. A new array, nums3, is formed by taking the bitwise XOR of every possible pair of elements (a, b) where a is from nums1 and b is from nums2. The goal is to return the bitwise XOR of all elements in nums3. If nums1 has length $M$ and nums2 has length $N$, nums3 will have $M imes N$ elements.

Why is this asked in interviews?

Companies like Meta and Google ask this to see if you can use the properties of the XOR operation to avoid unnecessary work. The brute-force approach takes $O(M imes N)$ time, but the optimized approach takes $O(M + N)$. It tests your understanding of the associative and commutative properties of XOR, and specifically the property that x ^ x = 0.

Algorithmic pattern used

This is a Brainteaser / Bit Manipulation problem. Consider how many times each element from nums1 appears in the final XOR sum. Each element a in nums1 will be XORed with every element in nums2. So, a appears $N$ times (the length of nums2). Similarly, each element b in nums2 appears $M$ times.

• If $N$ is even, a ^ a ^ ... ^ a ($N$ times) = 0.
• If $N$ is odd, a ^ a ^ ... ^ a ($N$ times) = a. The same logic applies to nums2.

Example explanation

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

• 1 is XORed with 3 and 4. (Appears 2 times)
• 2 is XORed with 3 and 4. (Appears 2 times)
• 3 is XORed with 1 and 2. (Appears 2 times)
• 4 is XORed with 1 and 2. (Appears 2 times) Since both lengths are 2 (even), every number appears an even number of times. XORing anything an even number of times results in 0. The final answer is 0. If nums1 = [1] and nums2 = [3, 4], 1 appears 2 times (0), but 3 and 4 appear 1 time each. Result = 3 ^ 4.

Common mistakes candidates make

The most common mistake is implementing the $O(M imes N)$ nested loop. Another is miscounting the occurrences—thinking an even length means the value is even, rather than the count of XOR operations.

Interview preparation tip

XOR is its own inverse. This means that if you XOR the same value twice, you're back to where you started. Always look for "even counts" in XOR problems to see if they cancel out to zero.