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

Find XOR Sum of All Pairs Bitwise AND

Number: 1963

Difficulty: Hard

Paid? No

Companies: Mobisy

Problem Description

Given two 0-indexed arrays arr1 and arr2 of non-negative integers, consider the list formed by performing bitwise AND on every pair (arr1[i], arr2[j]). The task is to compute the XOR sum of all these results. The XOR sum for a list is defined as the bitwise XOR of all its elements.

Key Insights

  • The problem asks for the XOR of (arr1[i] AND arr2[j]) for all valid pairs.
  • Instead of iterating over all pairs (which is computationally expensive), we can solve the problem by analyzing the contribution of each individual bit.
  • For each bit position, the number of times this bit is set in the results is determined by the number of elements in arr1 and arr2 that have that bit set.
  • The bit will contribute to the final XOR if and only if the multiplication of the counts of set bits in arr1 and arr2 (for that particular bit) is odd.
  • This observation leads us to the equivalence: the final result is (XOR of all elements in arr1) AND (XOR of all elements in arr2).

Space and Time Complexity

Time Complexity: O(n + m), where n and m are the lengths of arr1 and arr2 respectively. Space Complexity: O(1), apart from the input storage.

Solution

The solution involves the following steps:

  1. Compute the XOR of all the numbers in arr1.
  2. Compute the XOR of all the numbers in arr2.
  3. The result is the bitwise AND of the two XORs calculated above.

This works because for each bit position, the parity (odd/even) of the count of set bits in the XOR of an array reflects whether an odd number of elements contributed a 1 in that bit. Thus, a bit will be 1 in the final answer if and only if it appears an odd number of times in both arrays, which is captured by performing a bitwise AND on the XORs of each array.

Code Solutions

# Python solution
class Solution:
    def getXORSum(self, arr1, arr2):
        # Compute XOR for arr1
        xor1 = 0
        for num in arr1:
            xor1 ^= num  # XOR each element in arr1
        
        # Compute XOR for arr2
        xor2 = 0
        for num in arr2:
            xor2 ^= num  # XOR each element in arr2
        
        # The final answer is the bitwise AND of the two XORs
        return xor1 & xor2

# Example usage:
# solution = Solution()
# print(solution.getXORSum([1,2,3], [6,5]))  # Output: 0
← Back to All Questions