Perfect squares are numbers like 1, 4, 9 and 16. Each one is a whole number multiplied by itself. Numbers such as 3 and 11 are not perfect squares.
You are given a number n. Write n as a sum of perfect squares. You may use the same square many times. Return the smallest count of squares you need.
Examples
Example 1:
Input: n = 14
Output: 3
Explanation: 14 = 9 + 4 + 1, which uses 3 squares. No 2 squares add up to 14.
Example 2:
Input: n = 18
Output: 2
Explanation: 18 = 9 + 9, which uses 2 squares.
Example 3:
Input: n = 23
Output: 4
Explanation: 23 = 9 + 9 + 4 + 1, which uses 4 squares. Three squares are not enough.