TopCoder problem "SumOfSquareRoots" used in SRM 212 (Division I Level Two)



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

Writer:

legakis

Testers:

PabloGilberto , lbackstrom , brett1479

Problem categories:

Math, Simple Search, Iteration