DivisibleSetDiv2 | Topcoder Archive

Problem Statement

You are given a int[] b containing a sequence of n positive integers: b[0], ..., b[n-1]. We are now looking for another sequence a[0], ..., a[n-1]. This sequence should have the following properties:

Each a[i] should be a number of the form 2^x[i] where x[i] is some positive integer. In other words, each a[i] is one of the numbers 2, 4, 8, 16, ...
For each i, the value a[i]^b[i] (that is, a[i] to the power b[i]) should be divisible by P, where P is the product of all a[i].

Determine whether there is at least one sequence with the desired properties. Return "Possible" (quotes for clarity) if such a sequence exists and "Impossible" otherwise.

Definition

Class:: DivisibleSetDiv2
Method:: isPossible
Parameters:: int[]
Returns:: String
Method signature:: String isPossible(int[] b)
(be sure your method is public)

Constraints

b will contain between 1 and 50 elements, inclusive.
Each element in b will be between 1 and 10, inclusive.

Examples

```
{3,2}
```
```
Returns: "Possible"
```
One valid sequence is the sequence {2, 2}. That is, a[0] = a[1] = 2. Clearly, each a[i] is a power of two not smaller than 2. The product of all a[i] is 2*2 = 4. Both a[0]^b[0] = 2^3 = 8 and a[1]^b[1] = 2^2 = 4 are divisible by 4.
```
{3,3,3}
```
```
Returns: "Possible"
```
Here, one valid sequence is {2, 2, 2}.
```
{1,10}
```
```
Returns: "Impossible"
```
Suppose that a[0] = x and a[1] = y. The value a[0]^b[0] = x^1 should be divisible by x*y. This is only possible for y = 1. However, 1 is not a positive power of two, so we cannot have a[1] = 1.
```
{2, 3, 10}
```
```
Returns: "Possible"
```
One valid sequence is {8, 4, 2}.
```
{7,10,4,6,3}
```
```
Returns: "Possible"
```
```
{9,9,9,9,9,9,9,9,9}
```
```
Returns: "Possible"
```
```
{3,4,5,6,7}
```
```
Returns: "Impossible"
```

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.