LCMGCD | Topcoder Archive

Problem Statement

You are given the int[] x: a list containing n integers. Each element of x is a positive integer of the form 2^a * 3^b, where a and b are some nonnegative integers. The elements of x are not necessarily distinct.

You are going to perform n-1 operations. Each operation will consist of the following steps:

Choose two distinct indices into your list. Let X and Y be the numbers at those indices. Remove both of them from the list. (Note that X and Y are allowed to have the same value.)
Compute one of two possible values: either the greatest common divisor (gcd) of X and Y, or the least common multiple (lcm) of X and Y.
Append the computed value to your list.

Obviously, after n-1 operations you will be left with a single integer.

In addition to x you are given the int t. You would like to know whether it is possible to perform the sequence of operations on x in such a way that the final integer will be t. If it is possible, return "Possible", otherwise return "Impossible".

Definition

Class:: LCMGCD
Method:: isPossible
Parameters:: int[], int
Returns:: String
Method signature:: String isPossible(int[] x, int t)
(be sure your method is public)

Constraints

x will contain between 1 and 50 elements, inclusive.
Each element of x will be between 1 and 10^9, inclusive.
t will be between 1 and 10^9, inclusive.
t and each element of x will be of the form 2^i*3^j for some nonnegative i,j.

Examples

```
{2,3}
```
```
6
```
```
Returns: "Possible"
```
We can take the lcm to reach the goal.
```
{4,9}
```
```
6
```
```
Returns: "Impossible"
```
We have lcm(4,9) = 36 and gcd(4,9) = 1. It's impossible to get 6.

{6,12,24,18,36,72,54,108,216}

Returns: "Possible"

```
{6,27,81,729}
```
```
6
```
```
Returns: "Impossible"
```

{1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,
 1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1}

Returns: "Possible"

{72,16,16,16,16,16,27,27,27,27,27,27,27,27,27}

Returns: "Possible"

```
{100663296, 544195584, 229582512, 59049}
```
```
60466176
```
```
Returns: "Possible"
```
Watch out for integer overflow. The intermediate results won't always fit into a 32-bit integer variable.

{2,4,8,16,32,64}

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.