408301: GYM103091 A Happy XOR, Sad XOR

A Stanford researcher has been trying to figure out a new way to measure the happiness of undergraduate students. They surveyed $$$N$$$ students and stored their reported happiness levels in an array.

You are given an array of size $$$N$$$ with integer values. We want to partition the array into one or more contiguous subarrays. The happiness level of a partition is the sum of the bitwise XOR of the numbers in each subarray. We want to compute the maximum happiness and the minimum happiness possible with this array. Output the difference between these values.

Definitions: A subarray is defined as a contiguous segment of an array. In array: [4, 3, 7, 2, 1] some subarrays are [4, 3, 7] and [7, 2]. [4, 2, 1] is not a subarray.

The bitwise XOR (Exclusive Or), is an operator similar to addition. However, it is performed on each bit of a number. For each bit in a number, the XOR of the two bits are 0, if the arguments are the same, else the XOR is 1. XOR(0,0) = 0 XOR(1,1) = 0 XOR(1,0) = 1 XOR(0,1) = 1

The first line of input holds a single integer $$$N$$$ ($$$1\le N\le 10,000$$$). The next $$$N$$$ lines each contain a single value $$$v_i$$$ ($$$1\le v_i\le 2^{20}$$$), which are the values in the array.

Print, on a single line, an integer representing the difference between the minimum happiness and the maximum happiness attainable.

4
2
8
12
4

24

10
489
104
776
546
557
322
37
408
620
620

3846