Bitwise XOR of All Pairings
Problem
Given two arrays nums1 (length m) and nums2 (length n), form nums3 as the XOR of every pairing nums1[i] ^ nums2[j] — all m × n of them. Return the bitwise XOR of all numbers in nums3.
The trick: across those m × n XORs, each nums1[i] appears exactly n times and each nums2[j] appears exactly m times. Since v ^ v = 0, a value cancels when it is repeated an even number of times, and survives only when repeated an odd number of times.
nums1 = [2,1,3], nums2 = [10,2,5,0]13def xorAllNums(nums1, nums2):
m, n = len(nums1), len(nums2)
ans = 0
# each nums2[j] is paired with all m of nums1,
# so it appears m times; keep it only if m is odd
if m % 2 == 1:
for v in nums2:
ans ^= v
# each nums1[i] appears n times; keep it only if n is odd
if n % 2 == 1:
for v in nums1:
ans ^= v
return ansfunction xorAllNums(nums1, nums2) {
const m = nums1.length, n = nums2.length;
let ans = 0;
// each nums2[j] is paired with all m of nums1,
// so it appears m times; keep it only if m is odd
if (m % 2 === 1) {
for (const v of nums2) ans ^= v;
}
// each nums1[i] appears n times; keep it only if n is odd
if (n % 2 === 1) {
for (const v of nums1) ans ^= v;
}
return ans;
}int xorAllNums(int[] nums1, int[] nums2) {
int m = nums1.length, n = nums2.length;
int ans = 0;
// each nums2[j] is paired with all m of nums1,
// so it appears m times; keep it only if m is odd
if (m % 2 == 1) {
for (int v : nums2) ans ^= v;
}
// each nums1[i] appears n times; keep it only if n is odd
if (n % 2 == 1) {
for (int v : nums1) ans ^= v;
}
return ans;
}int xorAllNums(vector<int>& nums1, vector<int>& nums2) {
int m = nums1.size(), n = nums2.size();
int ans = 0;
// each nums2[j] is paired with all m of nums1,
// so it appears m times; keep it only if m is odd
if (m % 2 == 1) {
for (int v : nums2) ans ^= v;
}
// each nums1[i] appears n times; keep it only if n is odd
if (n % 2 == 1) {
for (int v : nums1) ans ^= v;
}
return ans;
}Explanation
Building nums3 directly would cost O(m · n) entries — up to 1010 for the constraints. Instead we reason about how many times each original value contributes to the final XOR.
XOR is associative and commutative (so order does not matter), and v ^ v = 0 (so a value pairs off with its own copy). Therefore a value XORed an even number of times vanishes, and one XORed an odd number of times contributes itself exactly once.
In the full set of pairings, every nums1[i] is matched against all n elements of nums2, so it appears n times. Symmetrically, every nums2[j] appears m times. So the whole of nums1 survives only when n is odd, and the whole of nums2 survives only when m is odd.
The answer is therefore: XOR of nums2 when m is odd, XOR-ed together with the XOR of nums1 when n is odd. Each surviving group is folded with a simple running ans ^= v.
Example: nums1 = [2,1,3] (m = 3, odd) and nums2 = [10,2,5,0] (n = 4, even). The even n wipes out nums1; the odd m keeps nums2, giving 10 ^ 2 ^ 5 ^ 0 = 13.