Problem

You are given two 0-indexed arrays, nums1 and nums2, consisting of non-negative integers. There exists 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.

Examples

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

Solution

Video explanation

Here is the video explaining this method in detail. Please check it out:

Method 1 - Naive

The naive approach involves directly computing the XOR of all pairings between elements of nums1 and nums2, just as described in the problem statement.

Here is the approach:

  1. Initialize a variable to store the result of XORs, starting with 0.
  2. Iterate through each element in nums1.
  3. For each element in nums1, iterate through each element in nums2.
  4. Compute the bitwise XOR of the current pair and update the result by XORing it with the computed value.
  5. Return the final result after iterating through all pairings.

Pseudocode

function xorAllNums(nums1, nums2):
    result = 0

    for each num1 in nums1:
        for each num2 in nums2:
            pair_xor = num1 ^ num2
            result = result ^ pair_xor

    return result

Complexity

  • ⏰ Time complexity: O(m * n), where m is the length of nums1 and n is the length of nums2. This is because we have an outer loop iterating over nums1 and an inner loop iterating over nums2, resulting in m * n iterations.
  • 🧺 Space complexity: O(1)

Method 2 - Optimal

Code

Java
class Solution {
    public int xorAllNums(int[] nums1, int[] nums2) {
        int ans = 0;

        // Check if the length of nums1 is odd
        if (nums1.length % 2 != 0) {
            for (int num : nums2) {
                ans ^= num;
            }
        }

        // Check if the length of nums2 is odd
        if (nums2.length % 2 != 0) {
            for (int num : nums1) {
                ans ^= num;
            }
        }

        return ans;
    }
}
Python
class Solution:
    def xorAllNums(self, nums1: List[int], nums2: List[int]) -> int:
        ans: int = 0

        # Check if the length of nums1 is odd
        if len(nums1) % 2 != 0:
            for num in nums2:
                ans ^= num

        # Check if the length of nums2 is odd
        if len(nums2) % 2 != 0:
            for num in nums1:
                ans ^= num

        return ans

Complexity

  • ⏰ Time complexity: O(m + n), where m is the length of nums1 and n is the length of nums2. This is because we need to iterate through both arrays once to compute their XORs.
  • 🧺 Space complexity: O(1), as we are utilizing only a constant amount of extra space for storing the XOR values and intermediate results.