16_Bitwise_XOR_of_All_Pairings.cpp

// 2425. Bitwise XOR of All Pairings

// 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 <= 105
// 0 <= nums1[i], nums2[j] <= 109

class Solution
{
public:
    int xorAllNums(vector<int> &nums1, vector<int> &nums2)
    {
        int x = 0, y = 0;
        for (int a : nums1)
        {
            x ^= a;
        }

        for (int b : nums2)
        {
            y ^= b;
        }

        return (nums1.size() % 2 * y) ^ (nums2.size() % 2 * x);
    }
};

/*
This code efficiently calculates the XOR of all possible pairs between two arrays nums1 and nums2.
Instead of explicitly calculating all pairs, it uses a mathematical property of XOR:
1. Variable x stores XOR of all elements in nums1
2. Variable y stores XOR of all elements in nums2
3. Final formula: If nums1.length is odd, include y; if nums2.length is odd, include x
This works because:
- If array length is even, each element appears even times in pairs (cancels out in XOR)
- If array length is odd, each element appears odd times in pairs (remains in XOR)
Time complexity: O(n + m) where n and m are lengths of nums1 and nums2
*/