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:

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.

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:

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

On the other hand:

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?

xxxxxxxxxx

var assert = require('assert');

​

function howManySquares(n) {

  return n;

}

​

try {

  assert.deepEqual(howManySquares(12), 3);

​

  console.log('PASSED: ' + 'howManySquares(12) should return 3');

} catch (err) {

  console.log(err);

}

​

try {

  assert.deepEqual(howManySquares(1), 1);

​

  console.log('PASSED: ' + 'howManySquares(1) should return 1');

} catch (err) {

  console.log(err);

}

​

try {

  assert.deepEqual(howManySquares(966), 3);

​

  console.log('PASSED: ' + 'howManySquares(966) should return 3');

} catch (err) {

  console.log(err);

}

Here's our guided, illustrated walk-through.

How do I use this guide?