NeetCode #865LC-2425MediumBit Manipulation
← Back to All Problems#865 · #2425 · Bitwise XOR of All Pairings(所有数对的异或值总和)
📌 Problem Statement & Constraints
You are given two 0-indexed arrays
nums1 and nums2 of non-negative integers. Consider every pairing (i, j) with 0 <= i < n and 0 <= j < m, and let nums3 contain the XOR of each such pair. Return the bitwise XOR of all elements of nums3. Constraints: 1 <= nums1.length, nums2.length <= 10^5, 0 <= nums1[i], nums2[j] <= 10^9.💡 Core Algorithmic Approaches
- Each value
nums1[i]is XOR-ed with every value ofnums2, so it appears innums3exactlymtimes. - XOR-ing the same value an even number of times cancels it, so only odd multiplicities survive in the final answer.
- Therefore
nums1contributes only whenmis odd, andnums2contributes only whennis odd. - The answer is the XOR of the arrays whose opposite length is odd.
💻 Benchmark Python3 Implementation
class Solution:
def xorAllNums(self, nums1: List[int], nums2: List[int]) -> int:
res = 0
if len(nums2) % 2: # each nums1 value appears m times
for x in nums1:
res ^= x
if len(nums1) % 2: # each nums2 value appears n times
for x in nums2:
res ^= x
return res⚡ Complexity Deep Dive
⏱️ Time Complexity
O(n + m): one pass over each array.
💾 Space Complexity
O(1): a single accumulator.
⚠️ Interview Pitfalls & Follow-ups
- Building
nums3explicitly: it holdsn * mvalues, up to 10^10, which is impossible. - Swapping the parity conditions:
nums1's values appearmtimes, so they matter whennums2.lengthis odd, not whennums1.lengthis. - Assuming both arrays must have odd length: either array can contribute on its own; only the opposite length's parity decides.
- Forgetting that XOR is its own inverse: the whole cancellation argument rests on
x ^ x = 0.
⚡
Test muscle memory on this topic via 3-Layer Flashcards
Active Recall: Mentally formulate Prompt ➔ Math Derivation ➔ Benchmark Implementation in 3 minutes.