Today’s problem

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

Intuition

According to the question, the formular of the output would be:

$$ ans = \large{XOR}_{\small i = 1}^{\small n} \large{XOR}_{\small j = 1}^{\small m} nums1[i]\space xor \space nums2[j] $$

where $\large{XOR}$ means the operation that xor from $i$ to $n$. Here, $n$ means the length of $nums1$, and $m$ means the length of $nums2$. According to the properties of xor, xor satisfies the law of commutation and the law of association (more information can be seen here), so we can change the formular to:

$$ ans = \large{XOR}_{\small i = 1}^{\small n} (nums1[i]^m) \space xor \space \large{XOR}_{\small j = 1}^{\small m} (nums2[j]^n) $$

According to the property that $A\space xor A = 0$, we now know that the result would be:

$$ ans = \large{XOR}_{\small i = 1}^{\small n} (nums1[i]^{m \% 2}) \space xor \space \large{XOR}_{\small j = 1}^{\small m} (nums2[j]^{n \% 2}) $$

Approach

Iterate two arrays and apply the formular above.

Complexity

  • Time complexity: $O(N + M)$, N is the length of nums1, M is the length of nums2.

  • Space complexity: $O(1)$, no more space is used.

Code

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