Here is the interview question prompt, presented for reference.

A perfect square is a number made by squaring a whole number.

Some examples include 1, 4, 9, or 16, and so on -- because they are the squared results of 1, 2, 3, 4, etc. For example:

1^2 = 1
2^2 = 4
3^2 = 9
4^2 = 16
...

However, 15 is not a perfect square, because the square root of 15 is not a whole or natural number.

| Perfect Square | Factors | |:--------------:|:-------:| | 1 | 1 * 1 | | 4 | 2 * 2 | | 9 | 3 * 3 | | 16 | 4 * 4 | | 25 | 5 * 5 | | 36 | 6 * 6 | | 49 | 7 * 7 | | 64 | 8 * 8 | | 81 | 9 * 9 | | 100 | 10 * 10 |

Given some positive integer n, write a method to return the fewest number of perfect square numbers which sum to n.

The follow examples should clarify further:

var n = 28
howManySquares(n);
// 4
// 16 + 4 + 4 + 4 = 28, so 4 numbers are required

On the other hand:

var n = 16
howManySquares(n);
// 1
// 16 itself is a perfect square
// so only 1 perfect square is required

Constraints

• n <= 10000
• n will always be non zero positive integer
• Expected time complexity : O(n*sqrt(n))
• Expected space complexity : O(n)

You can see the full challenge with visuals at this link.