# Sansa and XOR

**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:** is contiguous subarray of while is not.

**Input Format**

First line contains an integer , number of the test cases.

The first line of each test case contains an integer , number of elements in the array.

The second line of each test case contains integers that are elements of the array.

**Constraints**

**Output Format**

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

**Sample Input**

1 2 3 4 5 |
2 3 1 2 3 4 4 5 7 5 |

**Sample Output**

1 2 |
2 0 |

**Explanation**

*Test case #00:*

*Test case #01:*

**Solution**

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

* is even*

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

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

Then, will appear once by its own and times within the other subarrays: .

Similarly for . It will appear once by its own and times within the other subarrays: .

will also appear once by its own and times within the other subarrays: .

will also appear once by its own and times within the other subarrays: .

Since is even and every integer and appears even times in the XOR equation, the end result of the equation will be when is even. This can be easily seen by rearranging the XOR equation:

* is odd*

For the case when is odd consider the array .

Then, will appear once by its own and times within the other subarrays: .

which is located at index will appear times with items to its left, once alone, times with items to its right and once together with all items: . Altogether a total of which is an even number of times. An integer that is XORed with its self an even number of times results in .

will appear once by its own and times within the other subarrays: .

In summary for the case that is odd we only need to XOR items at indices 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:

**Full code**

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 |
public class SansaAndXor { private static int solve(int[] a) { int n = a.length; if (n % 2 == 0) { return 0; } int ans = a[0]; for (int i = 2; i < n; i += 2) { ans ^= a[i]; } return ans; } public static void main(String[] args) throws FileNotFoundException { System.setIn(new FileInputStream(System.getProperty("user.home") + "/" + "in.txt")); Scanner in = new Scanner(System.in); int tests = in.nextInt(); for (int t = 0; t < tests; t++) { int n = in.nextInt(); int[] a = new int[n]; for (int i = 0; i < n; i++) { a[i] = in.nextInt(); } System.out.println(solve(a)); } } } |