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.
This approach involves directly simulating all possible pairings using nested loops. For each element in nums1, pair it with each element in nums2, compute the XOR, and accumulate these results into a final result. Given the constraints, this has a time complexity of O(n * m), where n and m are the lengths of nums1 and nums2, respectively.
This C code uses nested loops to iterate over each element from both nums1 and nums2 to calculate each pair's XOR, subsequently updating the result with these XOR values.
Time Complexity: O(n * m)
Space Complexity: O(1)
Utilize the properties of XOR and the problem constraints to simplify the computation. By observing that XOR of a number with itself is zero and XOR represents the sum in a binary field, the result can be deduced more efficiently. If any element in nums1 or nums2 appears an even number of times, its contribution to overall XOR cancels out. Thus, derive the result by selectively computing XORs based only on whether lengths are even or odd.
This optimized C code applies XOR on each element in nums1 and nums2. It uses logical conditions based on the even or odd length of the arrays to compute the necessary result, leveraging the mathematical properties of XOR.
Time Complexity: O(n + m)
Space Complexity: O(1)
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.
If the length of the nums2 array is odd, it means that each element in nums1 has been XORed an odd number of times with each element in nums2, so the final XOR result of the nums1 array is the XOR result of all elements in the nums1 array. If it is even, it means that each element in nums1 has been XORed an even number of times with each element in nums2, so the final XOR result of the nums1 array is 0.
Similarly, we can know the final XOR result of the nums2 array.
Finally, XOR the two results again to get the final result.
The time complexity is O(m+n). Where m and n are the lengths of the nums1 and nums2 arrays, respectively.
Python
Java
C++
Go
TypeScript
| Approach | Complexity |
|---|---|
| Direct Simulation with Nested Loops | Time Complexity: O(n * m) |
| Optimized XOR Properties | Time Complexity: O(n + m) |
| Quick Thinking + Bit Manipulation | — |
| 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 |
Bitwise XOR of All Pairings | 2 Simple Approaches | Dry Runs | Leetcode 2425 | codestorywithMIK • codestorywithMIK • 7,496 views views
Watch 9 more video solutions →Practice Bitwise XOR of All Pairings with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor