Bitwise XOR of All Pairings

There are 2 key parts in the question:

1. the order of XOR operations in an expression does not matter
2. if you XOR a number with itself an even number of times, the answer will always be 0

Using both these properties, if we take the first example where:

• nums1 = [2, 1, 3]
• nums2 = [10, 2, 5, 0]

We find that a possible nums3, which contains the bitwise XOR of all pairings between nums1 and nums2, is [8,0,7,2,11,3,4,1,9,1,6,3].

However, when we try return the bitwise XOR of all integers in nums3, since we know that each element in nums3 is just the result of a XOR operation between an element in nums1 and nums2, it means that 8 ^ 0 ^ 7 ^ 2 ^ 11 ^ 3 ^ 4 ^ 1 ^ 9 ^ 1 ^ 6 ^ 3 is equivalent to (2 ^ 10) ^ (2 ^ 2) ^ (2 ^ 5) ^ (2 ^ 0) ^ (1 ^ 10) ^ (1 ^ 2) ^ (1 ^ 5) ^ (1 ^ 0) ^ ... etc.

You may notice immediately that there is a pattern; the number of a times you bitwise XOR an element is equal to the number of elements in the opposite array;

e.g. (*2* ^ 10) ^ (*2* ^ 2) ^ (*2* ^ 5) ^ (*2* ^ 0) ^ (1 ^ 10) ^ (1 ^ 2) ^ ... etc. you see that you have to bitwise XOR nums1[0] = 2 4 times as nums2.size() = 4.

Since order does not matter, we can rearrange the expression:

(2 ^ 10) ^ (2 ^ 2) ^ (2 ^ 5) ^ (2 ^ 0) ^ (1 ^ 10) ^ ...
= (2 ^ 2 ^ 2 ^ 2) ^ (10 ^ 2 ^ 5 ^ 0) ^ (1 ^ 10) ^ ...
= 0 ^ (10 ^ 2 ^ 5 ^ 0) ^ (1 ^ 10) ^ ...

Following this, we realise that bitwise XORing an element $n$ times is equivalent to bitwise XORing an element $n \bmod 2$ times.

Therefore, my algorithm is to check for the length of both nums1 and nums2;

• if the length is even, then do nothing
• else if the length is odd, then bitwise XOR all the elements in the opposite array (since, if $n$ be the length, then $n \bmod 2 = 1$).

Then, there are 3 outcomes:

1. if the lengths of both arrays are even, return 0
2. if the length of one array is odd, return the bitwise XOR of all the elements in the even array
3. if the length of both arrays are odd, return the bitwise XOR of all elements in both arrays

code

class Solution {
public:
    int xorAllNums(vector<int>& nums1, vector<int>& nums2) {
        int temp1 = 0, temp2 = 0;
        if (nums1.size()%2 == 1) {
            temp2 = nums3[0];
            for (int i = 1; i < nums2.size(); ++i) {
                temp2 ^= nums2[i];
            }
        }
        if (nums2.size()%2 == 1) {
            temp1 = nums1[0];
            for (int i = 1; i < nums1.size(); ++i) {
                temp1 ^= nums1[i];
            }
        }
        int ans = temp1 ^ temp2;
        return ans;
    }
};

complexity

• time: O(n)
• space: O(1)