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

Approach 01:

#include <vector>
using namespace std;

class Solution {
public:
    int xorAllNums(vector<int>& nums1, vector<int>& nums2) {
        int resultXor = 0;

        // If nums2 has an odd number of elements, XOR all elements of nums1
        if (nums2.size() % 2 != 0) {
            for (int num : nums1) {
                resultXor ^= num;
            }
        }

        // If nums1 has an odd number of elements, XOR all elements of nums2
        if (nums1.size() % 2 != 0) {
            for (int num : nums2) {
                resultXor ^= num;
            }
        }

        return resultXor;
    }
};

from typing import List

class Solution:
    def xorAllNums(self, nums1: List[int], nums2: List[int]) -> int:
        resultXor = 0

        # If nums2 has an odd number of elements, XOR all elements of nums1
        if len(nums2) % 2 != 0:
            for num in nums1:
                resultXor ^= num

        # If nums1 has an odd number of elements, XOR all elements of nums2
        if len(nums1) % 2 != 0:
            for num in nums2:
                resultXor ^= num

        return resultXor

Time Complexity:

• Iteration Over nums1:

  If ‘nums2’ has an odd number of elements, we iterate over ‘nums1’, which takes \( O(n) \), where \( n \) is the size of ‘nums1’.

• Iteration Over nums2:

  If ‘nums1’ has an odd number of elements, we iterate over ‘nums2’, which takes \( O(m) \), where \( m \) is the size of ‘nums2’.

• Overall Time Complexity:

  The overall time complexity is \( O(n + m) \), where \( n \) and \( m \) are the sizes of ‘nums1’ and ‘nums2’, respectively.

Space Complexity:

• Auxiliary Space:

  We only use a constant amount of extra space (for ‘resultXor’), so the space complexity is \( O(1) \).

• Overall Space Complexity:

  The overall space complexity is \( O(1) \).