BitwiseAnd | Topcoder Archive

Problem Statement

For non-negative integers A and B, let A&B denote the bitwise AND operation. That is, for each i, the i-th bit of A&B in binary representation is 1 if and only if the i-th bits of A and B are 1.

We call a set of non-negative integers S cool if the following conditions are satisfied.

For any two distinct elements A, B in S, A&B > 0.
For any three distinct elements A, B, C in S, A&B&C = 0.

You are given a long[] subset and an int N. All elements in subset are distinct. Compute a cool set with N distinct elements such that the cool set contains each element of subset and each element is between 1 and 2^60 - 1, inclusive. Return one such cool set as a long[] with elements in increasing order. If there are multiple solutions, return the lexicographically smallest one. If there are no such cool sets, return an empty long[] instead.

Definition

Class:: BitwiseAnd
Method:: lexSmallest
Parameters:: long[], int
Returns:: long[]
Method signature:: long[] lexSmallest(long[] subset, int N)
(be sure your method is public)

Constraints

N will be between 3 and 50, inclusive.
subset will contain between 0 and N elements, inclusive.
Each element of subset will be between 1 and 2^60 - 1, inclusive.
All the elements in subset will be distinct.
Elements in subset will be sorted in increasing order.

Examples

```
{14, 20}
```
```
3
```
```
Returns: {14, 18, 20 }
```
There are several possible cool sets. For example, the following sets are cool and each of them contains all the elements of subset. {14, 18, 20} {14, 20, 26} {14, 20, 50} ... Among these sets, the first one is the lexicographically smallest one.
```
{11, 17, 20}
```
```
4
```
```
Returns: { }
```
There is no cool set because (11&20) equals 0.
```
{99, 157}
```
```
4
```
```
Returns: {99, 157, 262, 296 }
```
```
{1152921504606846975}
```
```
3
```
```
Returns: { }
```
The element in subset equals to 2^60-1. Note that each element of your cool set should be less than or equal to 2^60-1.
```
{}
```
```
5
```
```
Returns: {15, 113, 402, 676, 840 }
```
```
{1, 3, 5, 7, 9, 11}
```
```
6
```
```
Returns: { }
```

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.