PROBLEM STATEMENT
The French mathematician Joseph Lagrange proved that any positive integer may
be expressed as the sum of at most 4 square numbers.
Create a class FourSquares that contains the method express, which returns an
int[] of four numbers. The sum of the squares of each of the returned numbers
should equal the input number.
DEFINITION
Class: FourSquares
Parameter: int
Returns: int[]
Method signature (be sure your method is public): int[] express (int x);
NOTES
- Your returned int[] should be sorted in descending order; highest number first.
- Your returned int[] may contain the same number more than once, and may
contain zeroes, but may not contain negative numbers.
- If multiple representations exist, return the one that uses the highest
squares. See the examples for clarification.
TopCoder will insure the validity of the input. An input is valid if the
following criterion is met:
- The given int x will be between 1 and 1000, inclusive.
EXAMPLES
Input: 15
Output: {3,2,1,1}, since 3*3 + 2*2 + 1*1 + 1*1 = 9+4+1+1 = 15.
Input: 42
Output: {6,2,1,1}, because 6*6 + 2*2 + 1*1 + 1*1 = 42. Note that the
combination {5,4,1,0} also sums to 42, but the first is preferable because the
6 in the first answer is greater than the 5 in the second.
Input: 107
Output: {9,5,1,0}. Note that the combination {9,4,3,1} also sums to 107, but
the first answer is preferable because the 5 in the second position of the
first answer is greater than the 4 in the second position of the second answer.
Input: 348
Output: {18,4,2,2}