Question

2425. Bitwise XOR of All Pairings

中文文档

Description

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.

 

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

Solutions

Solution 1: Quick Thinking + Bit Manipulation

Since each element of the array will be XORed with each element of another array, we know that the result remains the same when the same number is XORed twice, i.e., $a \oplus a = 0$. Therefore, we only need to count the length of the array to know how many times each element is XORed with each element of another array.

If the length of the nums2 array is odd, it means that each element in nums1 has been XORed an odd number of times with each element in nums2, so the final XOR result of the nums1 array is the XOR result of all elements in the nums1 array. If it is even, it means that each element in nums1 has been XORed an even number of times with each element in nums2, so the final XOR result of the nums1 array is 0.

Similarly, we can know the final XOR result of the nums2 array.

Finally, XOR the two results again to get the final result.

The time complexity is $O(m+n)$. Where $m$ and $n$ are the lengths of the nums1 and nums2 arrays, respectively.

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

class Solution {
  public int xorAllNums(int[] nums1, int[] nums2) {
    int ans = 0;
    if (nums2.length % 2 == 1) {
      for (int v : nums1) {
        ans ^= v;
      }
    }
    if (nums1.length % 2 == 1) {
      for (int v : nums2) {
        ans ^= v;
      }
    }
    return ans;
  }
}

class Solution {
public:
  int xorAllNums(vector<int>& nums1, vector<int>& nums2) {
    int ans = 0;
    if (nums2.size() % 2 == 1) {
      for (int v : nums1) {
        ans ^= v;
      }
    }
    if (nums1.size() % 2 == 1) {
      for (int v : nums2) {
        ans ^= v;
      }
    }
    return ans;
  }
};

func xorAllNums(nums1 []int, nums2 []int) int {
  ans := 0
  if len(nums2)%2 == 1 {
    for _, v := range nums1 {
      ans ^= v
    }
  }
  if len(nums1)%2 == 1 {
    for _, v := range nums2 {
      ans ^= v
    }
  }
  return ans
}

function xorAllNums(nums1: number[], nums2: number[]): number {
  let ans = 0;
  if (nums2.length % 2 != 0) {
    ans ^= nums1.reduce((a, c) => a ^ c, 0);
  }
  if (nums1.length % 2 != 0) {
    ans ^= nums2.reduce((a, c) => a ^ c, 0);
  }
  return ans;
}