SpecialClique | Topcoder Archive

Problem Statement

In this problem we use "AND" to denote the bitwise-and operator. For example, (6 AND 5) = 4.

A collection C is called a clique if and only if it has the following properties:

C is non-empty.
The elements of C are positive integers. (They are not required to be distinct.)
Whenever x and y are two (not necessarily distinct) elements of C, the value (x AND y) is non-zero.

For example, {3}, {1,1,1}, {16,17,18,19}, and {3,6,5} are cliques, but {3,5,20} is not a clique because (3 AND 20) = 0.

A clique is called trivial if the bitwise-and of all its elements is non-zero. A clique that is not trivial is called special.

For example, the cliques {3}, {1,1,1} and {16,17,18,19} are trivial, and the cliques {3,6,5} and {3,3,6,5,6} are special.

You are given a long[] s that contains a collection of positive integers. We want to change s into a special clique by erasing some (possibly none, but not all) of its elements. Return "Possible" if this can be done, or "Impossible" if it cannot be done.

Definition

Class:: SpecialClique
Method:: exist
Parameters:: long[]
Returns:: String
Method signature:: String exist(long[] s)
(be sure your method is public)

Constraints

s will contain between 1 and 1,000 elements, inclusive.
Each element in s will be between 1 and 1,000,000,000,000,000,000 (10^18) inclusive.

Examples

```
{3,6,5,8,24,56}
```
```
Returns: "Possible"
```
We can erase the last three elements of s, producing the special clique {3,6,5}.
```
{6, 5, 8, 24, 56}
```
```
Returns: "Impossible"
```
Each clique we can produce from this s is a trivial clique.

{585858585858585858, 585858585858585858, 585858585858585858, 585858585858585858}

Returns: "Impossible"

Note that s may contain duplicates.

{2,3,5,7,11,13,17,19,23,29,31,37,41,43,47}

Returns: "Impossible"

{1,1,2,3,5,8,13,21,34,55,89,144,233,377,610,987,1597}

Returns: "Possible"

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.