Problem Statement

The expression "sqrt(12) + sqrt(48)" can be simplified as follows:

```    sqrt(12) + sqrt(48) = sqrt(4*3) + sqrt(16*3)
= 2*sqrt(3) + 4*sqrt(3)
= 6*sqrt(3)
= sqrt(36*3)
= sqrt(108)
```

Given a list of integers, A, return a second list of integers, B, such that the sum of the square roots of the elements in B equals the sum of the square roots of the elements in A. B should contain as few elements as possible. The list with the fewest elements is guaranteed to be unique. The elements in your returned list B should be sorted from smallest to largest.

A will be given as a int[]. Return B as a int[] also.

For example, given the integers { 9, 16, 25 }, the sum of the square roots is 3 + 4 + 5, which is 12. The sum of the square roots of the list { 121, 1 } is also 12, but there is an even shorter list: { 144 }, which is the correct answer.

Definition

 Class: SumOfSquareRoots Method: shortestList Parameters: int[] Returns: int[] Method signature: int[] shortestList(int[] A) (be sure your method is public)

Constraints

-A will contain between 1 and 50 elements, inclusive.
-Each element of A will be between 1 and 1000, inclusive.

Examples

0)

 `{12, 48}`
`Returns: { 108 }`
 This is the first example in the problem statement.
1)

 `{9, 16, 25}`
`Returns: { 144 }`
 This is the second example in the problem statement.
2)

 `{4, 3}`
`Returns: { 3,  4 }`
 The square root of 4 plus the square root of 3 is ~3.7320508. There is no way to express this as the square root of a single integer, so the correct answer is { 3, 4 }.
3)

 ```{1, 1, 1} ```
`Returns: { 9 }`
4)

 `{5, 3, 5}`
`Returns: { 3,  20 }`
5)

 `{1, 3, 5, 12, 20}`
`Returns: { 1,  27,  45 }`
6)

 `{1, 2, 4, 8, 16, 32, 64, 128, 256, 512 }`
`Returns: { 961,  1922 }`
7)

 ```{ 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48, 49, 50 }```
```Returns:
{ 13,  14,  15,  17,  19,  21,  22,  23,  26,  29,  30,  31,  33,  34,  35,  37,  38,  39,  41,  42,  43,  46,  47,  54,  63,  90,  99,  180,  300,  450,  784 }```

Problem url:

http://www.topcoder.com/stat?c=problem_statement&pm=2943

Problem stats url:

http://www.topcoder.com/tc?module=ProblemDetail&rd=5858&pm=2943

legakis

Testers:

PabloGilberto , lbackstrom , brett1479

Problem categories:

Math, Simple Search, Iteration