SGS Programming Challenge P1 - XOR in Computer Class

View as PDF

Submit solution


Points: 7 (partial)
Time limit: 1.0s
Memory limit: 256M

Author:
Problem type

Andy recently learned about the bitwise XOR operation in computer class.

One of Andy's friends owns an array ~a~, which has a length of ~N~. Andy wants to make his friend sad by XORing all of the numbers in ~a~ by a non-negative number ~x~ such that the sum of the sums of each subarray is minimal. Since Andy is not an expert at XOR, he asks you to find ~x~ for him. If multiple solutions exist for ~x~, output the smallest one.

Recall subarrays are consecutive subsequences. For example, the subarrays of the array ~[1, 2, 3]~ are ~[1], [2], [3], [1, 2], [2, 3], [1, 2, 3]~. The sum of the sums of each subarray for this array will be ~(1) + (2) + (3) + (1 + 2) + (2 + 3) + (1 + 2 + 3) = 20~.

Constraints

For all subtasks:

~1 \le N \le 2 \times 10^5~

~0 \le a_i \le 10^9~

Subtask 1 [30%]

~0 \le a_i \le 1~

Subtask 2 [70%]

No additional constraints.

Input Specification

The first line contains an integer ~N~.

The second line contains ~N~ integers, his friend's array ~a~.

Output Specification

Output the minimal solution for ~x~, which is the number that Andy wishes to know.

Sample Input 1

3
1 2 3

Sample Output 1

3

Explanation for Sample 1

After XORing by 3, the array becomes ~[2, 1, 0]~. The sum of the sums of each subarray is ~(2) + (1) + (0) + (2 + 1) + (1 + 0) + (2 + 1 + 0) = 10~. It can be shown that ~10~ is the smallest possible sum of the sums of each subarray.

Sample Input 2

7
7 9 10 43 56 2 4

Sample Output 2

10

Comments

There are no comments at the moment.