Subtask 1

Because ~a_i~ is never greater than ~1~, each ~a_i~ only has one bit. If we XOR a bit by ~1~, the bit will flip. If we XOR it by ~0~, it will stay the same. Thus, there are two options for one bit: not changing it or flipping it. Applying this to all bits in one position, all bits either remain unchanged (if ~x~ is ~0~) or are flipped (if ~x~ is ~1~). To calculate the subarray sums, we observe that the sum of all subarrays can be calculated using the formula ~\sum_{i=1}^N a_i(n-i+1)(i)~. We calculate the sums for when the bit is flipped and when it is not to check which is larger.

Time complexity: ~\mathcal{O}(N)~

Full solution

We can observe that the bits are independent, thus we can use our subtask 1 solution on each bit position separately, multiplying our answer by ~2^{n-1}~ for the ~n^\text{th}~ bit (this is the value of that bit) and adding the product to ~x~.

Time complexity: ~\mathcal{O}(N \log(\max a_i))~