AlgoDaily - Sum of Perfect Squares

Sum of Perfect Squares (Hard)

Good afternoon! Here's our prompt for today.

You may see this problem at Autodesk, Instacart, Linkedin, Paypal, Airbnb, Symantec, Roblox, Rubrik, Opendoor, Proofpoint, Expedia, and Qualtrics.

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 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:

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)

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) {

OUTPUT

Results will appear here.