SumOfXor | Topcoder Archive

Problem Statement

There are n cards, the i-th one has number x[i] write on it. And there are 2 bags. For each card, you must choose one bag and put that card into that bag.

Suppose the XOR of all numbers in bag 1 is s1, and the XOR of all numbers in bag 2 is s2, your goal is to find the maximal value of (s1 + s2). Note that it is ok if one bag contains no cards, in that case the XOR is 0.

Definition

Class:: SumOfXor
Method:: maxSum
Parameters:: long[]
Returns:: long
Method signature:: long maxSum(long[] x)
(be sure your method is public)

Notes

You can assume the result will fit into 64 bits signed integer.

Constraints

x will contain between 1 and 1,000 elements, inclusive.
Each element in x will be between 0 and 1,000,000,000,000,000 (i.e. 10^15), inclusive.

Examples

```
{1,3,2}
```
```
Returns: 6
```
We need to put {1,2} into one bag and {3} into another, then we can get 3+3 = 6.
```
{1,2,4,8,16,32}
```
```
Returns: 63
```
One optimal solution is to put everything into one bag.

{123,456,789,101112,131415,161718,192021}

Returns: 323412

{1000000000000000,1000000000000000,1000000000000000,1000000000000000}

Returns: 2000000000000000

```
{0}
```
```
Returns: 0
```

This problem statement is the exclusive and proprietary property of Topcoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of Topcoder, Inc. is strictly prohibited. (c)2024, Topcoder, Inc. All rights reserved.