We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Bitwise XOR of All Pairings

Number: 2533

Difficulty: Medium

Paid? No

Companies: Trilogy

Problem Description

Given two 0-indexed arrays, nums1 and nums2, containing non-negative integers, we consider an array nums3 that contains the bitwise XOR of all pairings (every combination where one element is taken from nums1 and one from nums2). The task is to return the bitwise XOR of all numbers in nums3.

Key Insights

  • Each element in nums1 is paired with every element in nums2 exactly once.
  • In the overall XOR, any number that appears an even number of times cancels itself.
  • Every element in nums1 is used |nums2| times; thus, if |nums2| is even, the contributions of nums1 vanish.
  • Similarly, every element in nums2 is used |nums1| times; if |nums1| is even, the contributions of nums2 vanish.
  • If |nums2| is odd, then the XOR of all elements in nums1 remains. Similarly, if |nums1| is odd, then the XOR of all elements in nums2 remains.
  • The final answer is the XOR of these contributions.

Space and Time Complexity

Time Complexity: O(n + m), where n = length of nums1 and m = length of nums2.
Space Complexity: O(1) (ignoring input storage).

Solution

The solution leverages the cancellation property of XOR when an element appears an even number of times. For every x in nums1, note it appears |nums2| times in the overall XOR. Therefore, if |nums2| is odd, then the XOR of all values in nums1 persists; otherwise, they cancel out. The same reasoning applies to the elements in nums2 if |nums1| is odd. We then combine these results by taking the XOR of the two contributions. This approach avoids explicitly computing the pairwise XORs, achieving an efficient solution.

Code Solutions

# Function to compute the XOR of all pairings as described
def xorAllNums(nums1, nums2):
    # Initialize result for nums1 and nums2
    xor_nums1 = 0
    xor_nums2 = 0
    
    # If the length of nums2 is odd, we calculate the XOR across all elements in nums1.
    if len(nums2) % 2 == 1:
        for num in nums1:
            xor_nums1 ^= num   # XOR all elements in nums1
    
    # If the length of nums1 is odd, we calculate the XOR across all elements in nums2.
    if len(nums1) % 2 == 1:
        for num in nums2:
            xor_nums2 ^= num   # XOR all elements in nums2
    
    # The final answer is the XOR of the two contributions.
    return xor_nums1 ^ xor_nums2

# Example usage:
print(xorAllNums([2,1,3], [10,2,5,0]))  # Expected output: 13
← Back to All Questions