Get Time

   Problem Statement  

 Problem Statement for SpecialClique

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.


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


-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.


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.
Returns: "Impossible"
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)2010, TopCoder, Inc. All rights reserved.

This problem was used for:
       2016 TCO Algorithm Algo Semifinal 2 - Division I, Level One