Bitwise XOR of All Pairings — Solution in Python, Java & C++
Bitwise XOR of All Pairings solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem.
Bitwise XOR of All Pairings is a medium coding problem on arrays, bit manipulation and brainteaser, asked in Amazon, Google and Adobe interviews.
- Difficulty: Medium
- Topics: Arrays, Bit Manipulation, Brainteaser
- Asked at: Amazon, Google, Adobe
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
Form every pair (nums1[i], nums2[j]) and XOR the two values. Collect all nums1.length * nums2.length results into a list.
Return the XOR of everything in that list.
Example 1
Input: nums1 = [2,1,3], nums2 = [10,2,5,0]
Output: 13
Explanation: Twelve pairings whose XORs cancel down to 13.
Example 2
Input: nums1 = [1,2], nums2 = [3,4]
Output: 0
Explanation: Both lengths are even, so everything cancels.
Example 3
Input: nums1 = [7], nums2 = [3,5]
Output: 6
Explanation: 7 XOR 3 = 4 and 7 XOR 5 = 2, and 4 XOR 2 = 6.
Constraints
1 <= nums1.length, nums2.length <= 1000000 <= values <= 1000000000
Hints for Bitwise XOR of All Pairings
Hint 1
Building the list is
O(n·m)and far too slow. Count how many times each element is XOR-ed in.Hint 2
nums1[i]appears in exactlynums2.lengthpairings, and XOR-ing a value an even number of times cancels it.Hint 3
So
nums1contributes only whennums2.lengthis odd, and vice versa.
How to solve Bitwise XOR of All Pairings
XOR is its own inverse, so a value that appears an even number of times contributes nothing. Each element of nums1 appears once per element of nums2, which reduces the whole computation to two parity checks.
Approach
- If
nums2.lengthis odd, XOR every element ofnums1into the answer. - If
nums1.lengthis odd, XOR every element ofnums2into the answer. - Return the accumulated value.
Why it works
nums1[i] occurs in exactly m = nums2.length pairings. XOR-ing it m times gives nums1[i] when m is odd and 0 when m is even, because x ^ x = 0. The same argument applies to nums2 with n = nums1.length.
Complexity
- Time —
O(n + m) - Space —
O(1)
Pitfalls
- Materialising the pairings is
10^10operations at the stated limits. - Both conditions can hold at once — when both lengths are odd, both arrays contribute.
- Neither holding is also fine; the answer is then 0.
Reference solution
Python
from typing import List
def xorAllNums(nums1: List[int], nums2: List[int]) -> int:
out = 0
if len(nums2) % 2 == 1:
for x in nums1:
out ^= x
if len(nums1) % 2 == 1:
for x in nums2:
out ^= x
return outJava
public static int xorAllNums(int[] nums1, int[] nums2) {
int out = 0;
if (nums2.length % 2 == 1) {
for (int x : nums1) out ^= x;
}
if (nums1.length % 2 == 1) {
for (int x : nums2) out ^= x;
}
return out;
}C++
int xorAllNums(vector<int>& nums1, vector<int>& nums2) {
int out = 0;
if (nums2.size() % 2 == 1) {
for (int x : nums1) out ^= x;
}
if (nums1.size() % 2 == 1) {
for (int x : nums2) out ^= x;
}
return out;
}JavaScript
var xorAllNums = function(nums1, nums2) {
var out = 0;
if (nums2.length % 2 === 1) {
for (var i = 0; i < nums1.length; i++) out ^= nums1[i];
}
if (nums1.length % 2 === 1) {
for (var j = 0; j < nums2.length; j++) out ^= nums2[j];
}
return out;
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 1199 arrays problems · the whole catalogue
Learn the technique: Arrays · Bit Manipulation