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] <= 109This 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.
C++
Java
Python
C#
JavaScript
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.
C++
Java
Python
C#
JavaScript
Time Complexity: O(n + m)
Space Complexity: O(1)
| Approach | Complexity |
|---|---|
| Direct Simulation with Nested Loops | Time Complexity: O(n * m) |
| Optimized XOR Properties | Time Complexity: O(n + m) |
Bitwise XOR of All Pairings - Leetcode 2425 - Python • NeetCodeIO • 6,311 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