Thomas Ngo

Software Engineer

2 minute read

Problem Statement

problem

Brute Force [TLE]

class Solution:
    def xorAllNums(self, nums1: List[int], nums2: List[int]) -> int:
        res = 0
        for x in nums1:
            for y in nums2:
                res = res ^ x ^ y
        return res

Intuition

The problem involves finding the XOR of all elements resulting from the Cartesian product of two arrays. This can be simplified based on observations about the XOR operation:

  1. XOR is commutative and associative, allowing flexibility in the order of operations.
  2. Duplicating numbers in XOR cancels them out (e.g., (x \oplus x = 0)).
  3. The XOR of the Cartesian product depends on the lengths of the arrays and their parities (even or odd).

Approach

  1. Analyze the problem mathematically:
    • Each number in nums1 is XORed with all numbers in nums2, and vice versa.
    • If the length of an array is even, each number in the other array is XORed an even number of times and cancels out.
    • If the length is odd, every element contributes to the result exactly once.

  2. Identify cases based on array lengths:

    • Both nums1 and nums2 have even lengths: No contribution to the XOR result as all elements cancel out.
    • One of the arrays has an odd length: Contribute all elements of the other array to the XOR result.
    • Both arrays have odd lengths: All elements from both arrays contribute to the XOR result.
  3. Implement the logic:
    • Use simple loops to compute the XOR based on the identified cases.

Complexity

  • Time complexity:
    • (O(\max(n, m))), where (n = \text{len(nums1)}) and (m = \text{len(nums2)}). This is because, in the worst case, we iterate through one of the arrays entirely.
  • Space complexity:
    • (O(1)), as we only use a constant amount of additional space.

Code

class Solution:
    def xorAllNums(self, nums1: List[int], nums2: List[int]) -> int:
        res = 0
        n = len(nums1)
        m = len(nums2)
        if n % 2 == 0 and m % 2 == 0:
            res = 0
        elif n % 2 != 0 and m % 2 == 0:
            for x in nums2:
                res ^= x
        elif m % 2 != 0 and n % 2 == 0:
            for x in nums1:
                res ^= x
        else:
            for x in nums2:
                res ^= x
            for x in nums1:
                res ^= x
        return res

Editorial

Approach 1: Hash Map

class Solution:
    def xorAllNums(self, nums1: List[int], nums2: List[int]) -> int:
        # Get lengths of arrays
        len1, len2 = len(nums1), len(nums2)

        # Dictionary to store frequency of each number
        freq = {}

        # Add frequencies for nums1 elements
        # Each element appears n2 times in final result
        for num in nums1:
            freq[num] = freq.get(num, 0) + len2

        # Add frequencies for nums2 elements
        # Each element appears n1 times in final result
        for num in nums2:
            freq[num] = freq.get(num, 0) + len1

        # XOR numbers that appear odd number of times
        ans = 0
        for num in freq:
            if freq[num] % 2:
                ans ^= num

        return ans

Approach 2: Space Optimized Bit Manipulation

class Solution:
    def xorAllNums(self, nums1: List[int], nums2: List[int]) -> int:
        # Initialize XOR results for both arrays
        xor1, xor2 = 0, 0

        # Get lengths of both arrays
        len1, len2 = len(nums1), len(nums2)

        # If nums2 length is odd, each element in nums1 appears odd times in final result
        if len2 % 2:
            for num in nums1:
                xor1 ^= num

        # If nums1 length is odd, each element in nums2 appears odd times in final result
        if len1 % 2:
            for num in nums2:
                xor2 ^= num

        # Return XOR of both results
        return xor1 ^ xor2

You may also enjoy