Watch 10 video solutions for Bitwise XOR of All Pairings, a medium level problem involving Array, Bit Manipulation, Brainteaser. This walkthrough by codestorywithMIK has 7,496 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
You are given two 0-indexed arrays, nums1 and nums2, consisting of non-negative integers. There exists another array, nums3, which contains the bitwise XOR of all pairings of integers between nums1 and nums2 (every integer in nums1 is paired with every integer in nums2 exactly once).
Return the bitwise XOR of all integers in nums3.
Example 1:
Input: nums1 = [2,1,3], nums2 = [10,2,5,0] Output: 13 Explanation: 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 Explanation: 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 <= 1050 <= nums1[i], nums2[j] <= 109Problem Overview: You are given two integer arrays. For every pair (nums1[i], nums2[j]), compute nums1[i] XOR nums2[j], then return the XOR of all those results. A direct implementation forms every possible pairing, but the structure of XOR allows a much faster solution.
Approach 1: Direct Simulation with Nested Loops (O(n * m) time, O(1) space)
The straightforward method iterates through every element in nums1 and pairs it with every element in nums2. For each pair, compute a ^ b and accumulate it into a running XOR result. This approach uses two nested loops and exactly mirrors the problem statement, which makes it easy to reason about and useful for validating the logic on small inputs.
The downside is performance. If n and m are the lengths of the arrays, the algorithm performs n * m XOR operations. That quickly becomes expensive for larger inputs. Space usage stays constant because only a single accumulator variable is needed. This approach mainly demonstrates the brute-force baseline before applying bit manipulation insights.
Approach 2: Optimized XOR Properties (O(n + m) time, O(1) space)
XOR has two key properties: a ^ a = 0 and XOR is associative and commutative. When you expand the XOR of all pairings, each element in nums1 appears exactly len(nums2) times in the final expression, and each element in nums2 appears exactly len(nums1) times.
This leads to a parity observation. If len(nums2) is even, every value from nums1 is XORed an even number of times and cancels out. If it is odd, the XOR of all values in nums1 contributes once to the final result. The same reasoning applies symmetrically for nums2. Compute the XOR of each array individually, then include it in the answer only when the opposite array length is odd.
The algorithm becomes: compute xor1 = XOR(nums1) and xor2 = XOR(nums2). If len(nums2) is odd, include xor1. If len(nums1) is odd, include xor2. This reduces the work to two linear passes across the arrays. The approach relies heavily on properties of XOR and is a classic array + brainteaser style problem where algebraic reasoning eliminates the nested loops.
Recommended for interviews: Interviewers expect the XOR property optimization. The brute-force nested loops show that you understand the pairing definition, but the optimized approach demonstrates deeper knowledge of XOR behavior and reduces complexity from O(n * m) to O(n + m) with constant extra space.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Direct Simulation with Nested Loops | O(n * m) | O(1) | Useful for understanding the pairing definition or validating correctness on small inputs |
| Optimized XOR Properties | O(n + m) | O(1) | Preferred solution in interviews and production due to linear time and constant memory |