XorAndSum | Topcoder Archive

Problem Statement

You have a collection of cards. Each card contains a single non-negative integer. The integers written on the cards are not necessarily distinct. You are given a long[] number. Each element of number is a number written on one of the cards.

You may perform the following operation as many times as you want:

Choose two distinct cards. Let the numbers written on them be A and B, respectively.
Erase the number A and replace it with the number (A xor B). The number on the other card will remain unchanged (i.e., it will still be B).

Your goal is to maximize the sum of numbers written on your cards. Return the largest possible value of this sum.

Definition

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

Notes

The operator "xor" in the problem statement is the bitwise xor operation. For example, we have 9 xor 3 = 10, because 9 in binary is 1001, 3 in binary is 0011, and their bitwise xor is 1010 in binary, which is 10 in decimal.

Constraints

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

Examples

```
{1,0}
```
```
Returns: 2
```
One optimal solution is: change 0 into (1 xor 0) = 1. Then the sum will be 1+1 = 2.
```
{1,2,3}
```
```
Returns: 8
```
One optimal solution is: change 1 to (2 xor 1) = 3. Then the sum will be 3 + 2 + 3 = 8.
```
{0,0,0,0,0,0,0,0,0,0}
```
```
Returns: 0
```
We can't get any number other than 0.
```
{2,3,5,7,11,13,17,19}
```
```
Returns: 233
```

{123456789012345, 0, 0, 0, 0, 0, 0, 0, 0, 0}

Returns: 1234567890123450

{627,674,281,272,289,877,62,122,603,189,615}

Returns: 10742

```
{557}
```
```
Returns: 557
```

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.