Bitwise XOR of All Pairings — LeetCode 2425 Python Solution

The problem

You are given two 0-indexed arrays, nums1 and nums2, consisting of non-negative integers. Let there be 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).

Example

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].

Python solution

class Solution:
    def xorAllNums(self, nums1: List[int], nums2: List[int]) -> int:
        ans = 0
        if len(nums2) & 1:
            for v in nums1:
                ans ^= v
        if len(nums1) & 1:
            for v in nums2:
                ans ^= v
        return ans

Complexity

Pattern: Bit Manipulation

Use XOR, masks and the low-bit trick to replace whole data structures with an integer. LeetCode 2425. Bitwise XOR of All Pairings is filed here on both counts: the reference solution below belongs to the algorithm family this hub collects, and LeetCode tags it Bit Manipulation.

The bit manipulation guide has the Python template for the pattern and the 194 LeetCode problems that use it.

Related problems