2425. Bitwise XOR of All Pairings
Description
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 <= 105
0 <= nums1[i], nums2[j] <= 109
Solutions
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.
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.
1 2 3 4 5 6 7 8 9 10 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 |
|
1 2 3 4 5 6 7 8 9 10 |
|