SumOfSquareRoots | Topcoder Archive

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

```
{12, 48}
```
```
Returns: { 108 }
```
This is the first example in the problem statement.
```
{9, 16, 25}
```
```
Returns: { 144 }
```
This is the second example in the problem statement.
```
{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 }.
```
{1, 1, 1}
```
```
Returns: { 9 }
```
```
{5, 3, 5}
```
```
Returns: { 3,  20 }
```

{1, 3, 5, 12, 20}

Returns: { 1,  27,  45 }

{1, 2, 4, 8, 16, 32, 64, 128, 256, 512 }

Returns: { 961,  1922 }

{ 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 }

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.