Given a positive integer n, find the minimum number of perfect squares (1, 4, 9, 16, ..., repetitions allowed) that sum to exactly n.
A single line containing the integer n.
A single integer: the fewest perfect squares that sum to n.
Example 1
Input
12
Expected
3
Explanation
12 = 4 + 4 + 4 uses three squares, and no combination of one or two squares makes 12, so the answer is 3.
Example 2
Input
13
Expected
2
Explanation
13 = 4 + 9 uses two squares, and 13 is not itself a perfect square, so the answer is 2.
Ready to solve this?
Sign in to open the editor, run your code against the sample tests, and submit against the full test suite.
Sign in to solve →