XOR Sum

View as PDF

Submit solution

All submissions

Best submissions

Points: 10

Time limit: 0.6s

Memory limit: 256M

Author:

spencercompton

Problem type

Given an array of length $N$ ~N~, partition it into one or more contiguous groups. Once partitioned, take the XOR of the elements in each group. Compute the sum of these values. Bessie wants this sum to be minimal, Farmer John wants the sum to be maximal. Compute the difference between their sums.

Input Specification

The first line of the input will contain a single positive integer, $N$ ~N~. You may assume $N \le 10^5$ ~N \le 10^5~.

The second line of the input will contain $N$ ~N~ space-separated positive integers, the integers of the array in order. These positive integers will be less than $10^9$ ~10^9~.

Output Specification

Print on a single line the difference between the sums Bessie and Farmer John compute.

Sample Input

5
1 2 4 8 16

Sample Output

Comments

31

4fecta commented on Jan. 15, 2020, 4:20 a.m.

Fun relevant fact:

XOR got the symbol $\oplus$ ~\oplus~ from its similarity to the addition function. XOR essentially adds ( $+$ ~+~) the two bits at the same position of each number, then takes the result $\bmod 2$ ~\bmod 2~ ( $\bigcirc$ ~\bigcirc~). Quite interesting!

18

magicalsoup commented on Jan. 15, 2020, 4:48 a.m.

Damn, 4fecta here spitting out cool facts. What a chad.

14

p1geon commented on Jan. 15, 2020, 5:01 a.m.

on god :pray:

18

Aaeria commented on Jan. 15, 2020, 5:04 a.m.

This sounds like an usaco problem lol