Hoarding programming problems for you!

Looking for good programming challenges?

Use the search below to find our solutions for selected questions!

Sansa and XOR

Sharing is caring!

Problem statement
Sansa has an array. She wants to find the value obtained by XOR-ing the contiguous subarrays, followed by XOR-ing the values thus obtained. Can you help her in this task?

Note: \left[5,7,5\right] is contiguous subarray of \left[4,5,7,5\right] while \left[4,7,5\right] is not.

Input Format
First line contains an integer T, number of the test cases.
The first line of each test case contains an integer n, number of elements in the array.
The second line of each test case contains n integers that are elements of the array.

Constraints
1 \le T \le 5
2 \le n \le 10^{5}
1 \le numbers\ in\ array \le 10^{8}

Output Format
Print the answer corresponding to each test case in a separate line.

Sample Input

Sample Output

Explanation
Test case #00:
 1 \oplus 2 \oplus 3 \oplus (1 \oplus 2) \oplus (2 \oplus 3) \oplus (1 \oplus 2 \oplus 3) = 2

Test case #01:
 4 \oplus 5 \oplus 7 \oplus 5 \oplus (4 \oplus 5) \oplus (5 \oplus 7) \oplus (7 \oplus 5) \oplus (4 \oplus 5 \oplus 7) \oplus (5 \oplus 7 \oplus 5) \oplus (4 \oplus 5 \oplus 7 \oplus 5) = 0

Solution
We will solve our problem based on the fact whether n is even or odd.

n is even
First we will consider the case when n is even. For each x in the array we know that it appears 1 times by its own and n-1 times with the other numbers in the array during the XOR equation (see explanation above). Consider for example the following array:

\left[4, 5, 7, 5\right]

We will consider the two 5‘s as different. So we just rewrite the array as follows:

\left[4, 5, 7, 5^{*}\right]

Then, 4 will appear once by its own and n-1 times within the other subarrays: 4 \oplus (4 \oplus 5) \oplus (4 \oplus 5 \oplus 7) \oplus (4 \oplus 5 \oplus 7 \oplus 5^{*}).

Similarly for 5. It will appear once by its own and n-1 times within the other subarrays: (4 \oplus 5) \oplus 5 \oplus (5 \oplus 7) \oplus (5 \oplus 7 \oplus 5^{*}).

7 will also appear once by its own and n-1 times within the other subarrays: (4 \oplus 5 \oplus 7) \oplus (5 \oplus 7) \oplus 7 \oplus (7 \oplus 5^{*}).

5^{*} will also appear once by its own and n-1 times within the other subarrays:  (4 \oplus 5 \oplus 7 \oplus 5^{*}) \oplus (5 \oplus 7 \oplus 5^{*}) \oplus (7 \oplus 5^{*}) \oplus 5^{*}.

Since n is even and every integer 4, 5, 7 and 5^{*} appears even times in the XOR equation, the end result of the equation will be 0 when n is even. This can be easily seen by rearranging the XOR equation:

 4 \oplus 5 \oplus 7 \oplus 5^{*} \oplus (4 \oplus 5) \oplus (5 \oplus 7) \oplus (7 \oplus 5^{*}) \oplus (4 \oplus 5 \oplus 7) \oplus (5 \oplus 7 \oplus 5^{*}) \oplus (4 \oplus 5 \oplus 7 \oplus 5^{*}) = (4 \oplus 4 \oplus 4 \oplus 4) \oplus (5 \oplus 5 \oplus 5 \oplus 5) \oplus (7  \oplus 7 \oplus 7 \oplus 7)  \oplus (5^{*}\oplus 5^{*}\oplus 5^{*}\oplus 5^{*}) = 0 \oplus 0 \oplus 0 \oplus 0 = 0

n is odd
For the case when n is odd consider the array \left[1, 2, 3\right].
Then, 1 will appear once by its own and n-1 times within the other subarrays: 1 \oplus (1 \oplus 2) \oplus (1 \oplus 2 \oplus 3).

2 which is located at index i will appear i times with items to its left, once alone, (n-1)-i times with items to its right and once together with all items: (1 \oplus 2) \oplus 2 \oplus (2 \oplus 3) \oplus (1 \oplus 2 \oplus 3). Altogether a total of i + 1 + ((n-1)-i) + 1 = n+1 which is an even number of times. An integer that is XORed with its self an even number of times results in 0.

3 will appear once by its own and n-1 times within the other subarrays: (1 \oplus 2 \oplus 3) \oplus (2 \oplus 3) \oplus 3.

In summary for the case that n is odd we only need to XOR items at indices 0, 2, 4, 6, \dots since the elements at those indices appear an odd number of times. XORing an element with its self an odd number of times, results in that same number.

This can be easily seen by rearranging the XOR equation:

 1 \oplus 2 \oplus 3 \oplus (1 \oplus 2) \oplus (2 \oplus 3) \oplus (1 \oplus 2 \oplus 3) = (1 \oplus 1 \oplus 1) \oplus (2 \oplus 2 \oplus 2 \oplus 2) \oplus (3  \oplus 3 \oplus 3) = 1 \oplus 0 \oplus 3 = 2

Full code