EllysAndor | Topcoder Archive

Problem Statement

Elly has given you the following riddle:

"At the beginning, the variable X is set to zero. I will show you a sequence of cards. Each card will contain a positive integer. Each time I show you a card, you will have to choose exactly one of three possible actions. Let C be the number shown on the card. The three actions are:

Leave X unchanged.
Change X to (X OR C).
Change X to (X AND C).

Can you find a sequence of actions such that at the end the variable X will contain the value goal?"

You are given the int[] numbers and the int goal. The elements of numbers are the positive integers on Elly's cards, in the order in which she'll show them to you. Return "Possible" (quotes for clarity) if there is a sequence of actions after which X equals goal. Otherwise, return "Impossible".

Definition

Class:: EllysAndor
Method:: canGet
Parameters:: int[], int
Returns:: String
Method signature:: String canGet(int[] numbers, int goal)
(be sure your method is public)

Notes

Given two integers X and Y, the result of the bitwise operation X AND Y has 1-bits on all positions where both X and Y have 1-bit in their binary representation. For example 1337(10) AND 4213(10) = 49(10), since 0000010100111001(2) AND 0001000001110101(2) = 0000000000110001(2).
Given two integers X and Y, the result of the bitwise operation X OR Y has 1-bits on all positions where at least one of X and Y has 1-bit in its binary representation. For example 1337(10) OR 4213(10) = 5501(10), since 0000010100111001(2) OR 0001000001110101(2) = 0001010101111101(2).

Constraints

numbers will contain between 1 and 100 elements, inclusive.
Each element of numbers will be between 1 and 1,000,000,000, inclusive.
goal will be between 1 and 1,000,000,000, inclusive.

Examples

```
{42, 13, 29, 17}
```
```
25
```
```
Returns: "Possible"
```
You should choose the following sequence of actions: Start with X = 0. Change X to (X OR 42) = 42. Change X to (X AND 13) = 42 AND 13 = 8. Change X to (X AND 29) = 8 AND 29 = 8. Change X to (X OR 17) = 8 OR 17 = 25. Alternately, when processing the number 29, you could have left the variable X unchanged.
```
{13, 13, 42, 13, 13}
```
```
42
```
```
Returns: "Possible"
```
We can simply skip all the 13s, and use OR on the 42.
```
{1337, 666, 511, 4242, 666, 1234, 4321, 717}
```
```
193
```
```
Returns: "Possible"
```
A possible solution here would be to use AND, OR, OR, OR, AND, AND, OR, AND.
```
{1337, 666, 511, 4242, 666, 1234, 4321, 717}
```
```
2016
```
```
Returns: "Impossible"
```
This example has the same sequence of numbers as Example 2, but the goal is different. This new goal cannot be achieved.
```
{2, 4, 6, 8, 10, 12, 14, 16, 18, 20}
```
```
13
```
```
Returns: "Impossible"
```
Since all numbers are even, we are unable to reach an odd goal.

{
 795755685, 581869303, 404620563, 708632712, 545404205, 133711906, 372047868, 949333986, 579004999, 323567404,
 418932836, 944672732, 196140741, 809094427, 946129058, 30574577, 182506778, 15198493, 150802600, 138749191,
 676943010, 177512688, 126303054, 81133258, 183966551, 471852627, 84672537, 867128744, 857788837, 275731772,
 609397213, 20544910, 811450930, 483031419, 361913171, 547204602, 892462744, 522136404, 173978710, 131752569,
 478582453, 867889991, 153380496, 551745921, 647984700, 910208077, 283496852, 368550363, 379821990, 712568903,
 40498239, 113911604, 103237637, 39073007, 684602223, 812852787, 479711181, 746745228, 735241235, 296707007,
 262522458, 870676136, 136721027, 359573809, 189375153, 547914047, 198304613, 640439653, 417177802, 25475624,
 758242872, 764919655, 310701088, 537655880, 361931892, 14685971, 213794688
}

218021875

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.