SumOfSquareRoots
SRM 212 · 2004-09-25 · by legakis
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
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.
Constraints
- A will contain between 1 and 50 elements, inclusive.
- Each element of A will be between 1 and 1000, inclusive.
{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.
{3, 4}
Returns: { 3, 4 }
{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}
Returns: { 1 }
Submissions are judged against all 30 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Language: C++17 · define a public class SumOfSquareRoots with a public method vector<int> shortestList(vector<int> A) · 30 test cases · 2 s / 256 MB per case