Bitwise XOR of All Pairings

Today we are looking at one of the question involving bits and logic gates.

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.

This is my first time seeing this question. I believe this can be true for many of you.

My approach to solve any unknown question is to first try brute-force method.

Here, the question explicitly talks about XOR gates. So, before we move forward, we should know our XOR values. Below, is the XOR truth table.

INPUT A	INPUT B	OUTPUT
0	0	0
0	1	1
1	0	1
1	1	0

From the truth table, we conclude, if two values are same, they result in zero, meaning,

2 ^ 2 = 0b0010 ^ 0b0010 = 0b0000 = 0

Moving ahead to our question,I am taking some random array here, and see what we get if we XORed them.

Testing the case when one of the Array is odd-sized

nums1= [2,4,6,8]

nums2 =[3,6,9]

XORing nums1 and nums2, we get our nums3 array:

nums3 = [2 ^ 3, 2 ^ 6, 2 ^ 9, 4 ^ 3, 4 ^ 6, 4 ^ 9, 6 ^ 3, 6 ^ 6, 6 ^ 9, 8 ^ 3, 8 ^ 6, 8 ^ 9]

The question asks for the XOR of all elements in nums3. XORing all elements in nums3:

= 2 ^ 3 ^ 2 ^ 6 ^ 2 ^ 9 ^ 4 ^ 3 ^ 4 ^ 6 ^ 4 ^ 9 ^ 6 ^ 3 ^ 6 ^ 6 ^ 6 ^ 9 ^ 8 ^ 3 ^ 8 ^ 6 ^ 8 ^ 9

From the XOR truth table, we notice:

• Numbers that appear an even number of times cancel out.
• We are left with:
  = 2 ^ 4 ^ 6 ^ 8

Each element in nums1 is paired with every element in nums2. If the size of nums2 is odd, every element of nums1 will appear an odd number of times in nums3.
Similarly, if the size of nums1 is odd, every element of nums2 will appear an odd number of times in nums3.
If an element appears an odd number of times, it contributes to the XOR result. If it appears an even number of times, it cancels out.

Testing the Case When Both Arrays Are Even-Sized

Let’s test what happens when both arrays are even-sized:

nums1 = [2, 4, 6, 8]
nums2 = [3, 6, 9, 12]

Pairwise XORing nums1 and nums2 gives:

nums3 = [2 ^ 3, 2 ^ 6, 2 ^ 9, 2 ^ 12,
4 ^ 3, 4 ^ 6, 4 ^ 9, 4 ^ 12,
6 ^ 3, 6 ^ 6, 6 ^ 9, 6 ^ 12,
8 ^ 3, 8 ^ 6, 8 ^ 9, 8 ^ 12]

Here, all numbers appear an even number of times, and the XOR result is:

= 0

I am sure you would have caught on the pattern here. Every time we deal with even number of elements, we end up having 0.

Testing the Case When Both Arrays are odd-sized

Breaking it down, we have,

nums1 = [1, 3, 5]
nums2 = [7, 9, 11]

nums3 = [
1 ^ 7, 1 ^ 9, 1 ^ 11, // Pairing 1 with every element of nums2
3 ^ 7, 3 ^ 9, 3 ^ 11, // Pairing 3 with every element of nums2
5 ^ 7, 5 ^ 9, 5 ^ 11 // Pairing 5 with every element of nums2
]

nums1 Contribution:
Since nums2 has an odd size (3 elements), each number in nums1 is XORed with every element in nums2. This means every number in nums1 appears an odd number of times in nums3.
Example:

• 1 appears 3 times: (1 ^ 7), (1 ^ 9), (1 ^ 11)
• 3 appears 3 times: (3 ^ 7), (3 ^ 9), (3 ^ 11)
• 5 appears 3 times: (5 ^ 7), (5 ^ 9), (5 ^ 11)

Since each number in nums1 appears an odd number of times, the XOR result includes all elements of nums1.

nums2 Contribution:
Similarly, since nums1 has an odd size (3 elements), each number in nums2 is XORed with every element in nums1. This means every number in nums2 also appears an odd number of times in nums3.

Example:

• 7 appears 3 times: (1 ^ 7), (3 ^ 7), (5 ^ 7)
• 9 appears 3 times: (1 ^ 9), (3 ^ 9), (5 ^ 9)
• 11 appears 3 times: (1 ^ 11), (3 ^ 11), (5 ^ 11)

Since each number in nums2 appears an odd number of times, the XOR result also includes all elements of nums2.

XOR(nums1) = 1 ^ 3 ^ 5 = 7

XOR(nums2) = 7 ^ 9 ^ 11 = 3

XOR(nums3) = XOR(nums1) ^ XOR(nums2)
= 7 ^ 3
= 4

We notice that Odd-sized arrays ensure each element contributes an odd number of times, so all elements of both arrays are included in the XOR result.

Finally, coding this up,

class Solution {
public:
    // Helper function to compute XOR of all elements in an array
    int getArrayXor(const vector<int>& nums) {
        int ans = 0; // Initialize with 0, as XOR with 0 has no effect
        for (int num : nums) {
            ans ^= num; // Compute XOR of all elements
        }
        return ans;
    }

    int xorAllNums(vector<int>& nums1, vector<int>& nums2) {
        // Check if either array is empty
        if (nums1.empty() && nums2.empty()) {
            return 0;
        }
        if (nums1.empty()) {
            return getArrayXor(nums2);
        }
        if (nums2.empty()) {
            return getArrayXor(nums1);
        }

        // Determine parity of sizes
        bool nums1Odd = nums1.size() % 2 != 0; // True if nums1 is odd-sized
        bool nums2Odd = nums2.size() % 2 != 0; // True if nums2 is odd-sized

        // Return results based on parity
        if (nums1Odd && nums2Odd) {
            // Both arrays are odd-sized
            return getArrayXor(nums1) ^ getArrayXor(nums2);
        }
        if (nums1Odd) {
            // Only nums1 is odd-sized
            return getArrayXor(nums2);
        }
        if (nums2Odd) {
            // Only nums2 is odd-sized
            return getArrayXor(nums1);
        }

        // Both arrays are even-sized
        return 0;
    }
};

Alternative approach could be

class Solution {
public:
    int xorAllNums(vector<int>& nums1, vector<int>& nums2) {
        // Compute the XOR of all elements in nums1 and nums2
        int xorNums1 = 0, xorNums2 = 0;
        for (int num : nums1) {
            xorNums1 ^= num;
        }
        for (int num : nums2) {
            xorNums2 ^= num;
        }

        // Determine the parity of the array sizes
        bool nums1Odd = nums1.size() % 2 != 0;
        bool nums2Odd = nums2.size() % 2 != 0;

        // Compute the final result based on parity
        return (nums1Odd ? xorNums2 : 0) ^ (nums2Odd ? xorNums1 : 0);
    }
};

Complexity Analysis

1. Time Complexity:
   • O(n+m), where n is the size of nums1 and m is the size of nums2.
   • The XOR computation for both arrays is linear.
2. Space Complexity:
   • O(1), as no extra space is used apart from a few variables.

Is it very long? I hope not. Please do let me know via comment box!