⚡Flashcard Drill➔
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

  1. Each value nums1[i] is XOR-ed with every value of nums2, so it appears in nums3 exactly m times.
  2. XOR-ing the same value an even number of times cancels it, so only odd multiplicities survive in the final answer.
  3. Therefore nums1 contributes only when m is odd, and nums2 contributes only when n is odd.
  4. 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 nums3 explicitly: it holds n * m values, up to 10^10, which is impossible.
  • Swapping the parity conditions: nums1's values appear m times, so they matter when nums2.length is odd, not when nums1.length is.
  • 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.
🎯 Drill This Card Now➔

🧩 Related Bit Manipulation Problems