Bitwise XOR of All Pairings

main.md

Question

Approach

I began by exploring the properties of XOR operations. I know that XOR is both commutative and associative, which means the order of operations doesn’t matter. Additionally, XORing any number with (0) leaves the number unchanged, and XORing a number with itself results in (0). These properties became the foundation for my approach.

The insight I found is based on how the XOR operations are distributed in this problem. If (nums1) has (m) elements and (nums2) has (n) elements, then each number in (nums1) is XORed with all (n) numbers in (nums2), and each number in (nums2) is XORed with all (m) numbers in (nums1). Consequently, each number in (nums1) will appear (n) times in the XOR operations, and each number in (nums2) will appear (m) times.

This observation led me to an important optimization. If (n) (the length of (nums2)) is even, XORing a number (n) times effectively cancels it out, since XORing a number an even number of times results in (0). Similarly, if (m) (the length of (nums1)) is even, numbers in (nums2) will cancel out.

With this understanding, I first calculate the XOR of all numbers in (nums1) and (nums2) individually. Then, I check the lengths of (nums1) and (nums2). If (nums2) has an odd length, I include the XOR of (nums1) in the final result. Similarly, if (nums1) has an odd length, I include the XOR of (nums2) in the final result.

Implementation

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

Complexities

• Time: O(m+n), where m and n are the lengths of nums1 and nums2, respectively.
• Space: O(1) for contant space.