Minimum number of squares whose sum equals to a given number in JAVA

Starting from a number, we must return the minimum number of square numbers whose sum equals to that number.

​Input: int input = 12; Output: 3 Explanation: There are minimum 3 squares that summed equals 12: 4 + 4 + 4 = 12; 4 = 2*2.

Solution:

1. static int minimumSquares(int input) { 2. int[] minimumSquaresRequired = new int[input + 1]; 3. minimumSquaresRequired[1] = 1; 4. 5. for (int i = 2; i <= input; ++i) { 6. minimumSquaresRequired[i] = Integer.MAX_VALUE; 7. for (int j = 1; i - (j * j) >= 0; ++j) { 8. minimumSquaresRequired[i] = Math.min(minimumSquaresRequired[i], minimumSquaresRequired[i - (j * j)]); 9. } 10. minimumSquaresRequired[i] += 1; 11. } 12. return minimumSquaresRequired[input]; 13. } 14.