Mark As Completed Discussion

Good evening! Here's our prompt for today.

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:

SNIPPET
11^2 = 1
22^2 = 4
33^2 = 9
44^2 = 16
5...

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

Perfect SquareFactors
11 * 1
42 * 2
93 * 3
164 * 4
255 * 5
366 * 6
497 * 7
648 * 8
819 * 9
10010 * 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:

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

On the other hand:

JAVASCRIPT
1var n = 16
2howManySquares(n);
3// 1
4// 16 itself is a perfect square
5// 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)

Try to solve this here or in Interactive Mode.

How do I practice this challenge?

JAVASCRIPT
OUTPUT
:001 > Cmd/Ctrl-Enter to run, Cmd/Ctrl-/ to comment

Here's how we would solve this problem...

How do I use this guide?