Scale Engineer

Bitwise XOR of All Pairings

Med
#2209Time: O(N * M), where N is the length of `nums1` and M is the length of `nums2`. We iterate through every possible pair, making this quadratic in terms of input size.Space: O(1), as we only use a few variables to store the intermediate and final results, regardless of the input size.1 company
Patterns
Bit Manipulation
Data structures
Array
Companies
Trilogy

Prompt

You are given two 0-indexed arrays, nums1 and nums2, consisting of non-negative integers. Let there be another array, nums3, which contains the bitwise XOR of all pairings of integers between nums1 and nums2 (every integer in nums1 is paired with every integer in nums2 exactly once).

Return the bitwise XOR of all integers in nums3.

 

Example 1:

Input: nums1 = [2,1,3], nums2 = [10,2,5,0]
Output: 13
Explanation:
A possible nums3 array is [8,0,7,2,11,3,4,1,9,1,6,3].
The bitwise XOR of all these numbers is 13, so we return 13.

Example 2:

Input: nums1 = [1,2], nums2 = [3,4]
Output: 0
Explanation:
All possible pairs of bitwise XORs are nums1[0] ^ nums2[0], nums1[0] ^ nums2[1], nums1[1] ^ nums2[0],
and nums1[1] ^ nums2[1].
Thus, one possible nums3 array is [2,5,1,6].
2 ^ 5 ^ 1 ^ 6 = 0, so we return 0.

 

Constraints:

  • 1 <= nums1.length, nums2.length <= 105
  • 0 <= nums1[i], nums2[j] <= 109

Approaches

2 approaches with complexity analysis and trade-offs.

This approach directly simulates the process described in the problem. We generate all possible pairings of elements from nums1 and nums2, calculate the bitwise XOR for each pair, and then compute the bitwise XOR of all these results.

Algorithm

  • Initialize a variable xor_sum to 0.
  • Use a nested loop. The outer loop iterates through each element num1 in nums1.
  • The inner loop iterates through each element num2 in nums2.
  • Inside the inner loop, calculate the bitwise XOR of the current pair: pair_xor = num1 ^ num2.
  • Update the xor_sum by XORing it with the pair_xor: xor_sum = xor_sum ^ pair_xor.
  • After the loops complete, return xor_sum.

Walkthrough

This method involves a straightforward, brute-force implementation. We iterate through every element in nums1 and, for each of those, we iterate through every element in nums2. This creates all possible pairs. For each pair (num1, num2), we compute their bitwise XOR num1 ^ num2 and accumulate this value into a running total XOR sum. While simple to conceptualize, its performance degrades rapidly as the size of the input arrays increases.

class Solution {    public int xorAllNums(int[] nums1, int[] nums2) {        int xor_sum = 0;        for (int num1 : nums1) {            for (int num2 : nums2) {                xor_sum ^= (num1 ^ num2);            }        }        return xor_sum;    }}

Complexity

Time

O(N * M), where N is the length of `nums1` and M is the length of `nums2`. We iterate through every possible pair, making this quadratic in terms of input size.

Space

O(1), as we only use a few variables to store the intermediate and final results, regardless of the input size.

Trade-offs

Pros

  • Simple to understand and implement.

  • Directly follows the problem description without requiring mathematical insights.

Cons

  • Highly inefficient for large inputs.

  • Will not pass the time limits for the given constraints, leading to a 'Time Limit Exceeded' (TLE) error.

Solutions

class Solution : def xorAllNums ( self , nums1 : List [ int ], nums2 : List [ int ]) -> int : ans = 0 if len ( nums2 ) & 1 : for v in nums1 : ans ^= v if len ( nums1 ) & 1 : for v in nums2 : ans ^= v return ans

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next →

Next problem