2425. Bitwise XOR of All Pairings

#Problem

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.

https://leetcode.com/problems/bitwise-xor-of-all-pairings/

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 <= 10⁵
• 0 <= nums1[i], nums2[j] <= 10⁹

#Test Cases

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

import pytest

from solution import Solution


@pytest.mark.parametrize('nums1, nums2, expected', [
    ([2,1,3], [10,2,5,0], 13),
    ([1,2], [3,4], 0),
])
@pytest.mark.parametrize('sol', [Solution()])
def test_solution(sol, nums1, nums2, expected):
    assert sol.xorAllNums(nums1, nums2) == expected

#Thoughts

首先对于一个非负整数 x，偶数个 x 的 XOR 的结果为 0，奇数个 x 的 XOR 的结果为 x。

不妨设 nums1 的长度为 m，其元素分别为 $a_1,a_2,\dots,a_m$。nums2 的长度为 n，元素为 $b_1,b_2,\dots,b_n$。

那么所求的结果为：

所以如果 n 是偶数就取 0，否则取 nums1 中每个数字 XOR 的结果；如果 m 是偶数就取 0，否则取 nums2 中每个数字 XOR 的结果；这两个中间结果取 XOR 即可。

时间复杂度 O(m + n)，空间复杂度 O(1)。

#Code

from functools import reduce
import operator


class Solution:
    def xorAllNums(self, nums1: list[int], nums2: list[int]) -> int:
        res = 0
        if len(nums1) & 1: res = reduce(operator.xor, nums2, res)
        if len(nums2) & 1: res = reduce(operator.xor, nums1, res)
        return res