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