SubsetXor | Topcoder Archive

Problem Statement

Alice has a list (A) containing some positive integers. She asks Bob to pick any non-empty subset of numbers from the list and compute its XOR.

Bob writes down the computed value in a notebook. She asks him to pick subsets repeatedly until all subsets of the list are chosen at least once. Bob being intelligent, won't pick a previously chosen subset again.

Find the smallest positive number that Bob cannot write in his notebook.

Definition

Class:: SubsetXor
Method:: computeSmallest
Parameters:: long[]
Returns:: long
Method signature:: long computeSmallest(long[] A)
(be sure your method is public)

Notes

The XOR of an empty subset is defined to be 0 and the XOR of a subset with exactly 1 element is the number itself.

Constraints

The length of A will be between 1 and 1000, inclusive.
Each number in A will be between 1 (inclusive) and 262 (exclusive).
It is guaranteed that the answer would be between 1 (inclusive) and 263 (exclusive).

Examples

```
{2000, 300, 46}
```
```
Returns: 1
```
Bob would select the following subsets and write the corresponding XOR values: {2000} => 2000 {300} => 300 {46} => 46 {2000, 300} => 2000 ^ 300 = 1788 {300, 46} => 300 ^ 46 = 258 {2000, 46} => 2000 ^ 46 = 2046 {2000, 300, 46} => 2000 ^ 300 ^ 46 = 1746 The smallest positive number that Bob won't write in his notebook is 1.
```
{1, 2}
```
```
Returns: 4
```
Bob would write the XORs of subsets {1}, {2} and {1, 2} which are 1, 2 and 3 respectively. The smallest number that he won't write in his notebook is 4.

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.