1var assert = require('assert');
2
3function howManySquares(n) {
4  let perfectSqNumsLength = 1;
5  while (perfectSqNumsLength * perfectSqNumsLength < n) {
6    perfectSqNumsLength++;
7  }
8
9  if (perfectSqNumsLength * perfectSqNumsLength > n) {
10    perfectSqNumsLength--;
11  }
12
13  const perfectSqNums = [];
14
15  // Fill the array backwards so we get the numbers to work with
16  for (let i = perfectSqNumsLength - 1; i >= 0; i--) {
17    perfectSqNums[perfectSqNumsLength - i - 1] = (i + 1) * (i + 1);
18  }
19
20  // instantiate a hashmap of possible paths
21  const paths = {};
22  paths[1] = 1; // 1 = 1
23  paths[0] = 0; // 0 means you need 0 numbers to get 0
24
25  return numSquares(paths, perfectSqNums, n);
26}
27
28function numSquares(paths, perfectSqNums, n) {
29  if (paths.hasOwnProperty(n)) {
30    // we already knew the paths to add up to n.
31    return paths[n];
32  }
33
34  let min = Number.MAX_SAFE_INTEGER;
35  let thisPath = 0;
36
37  for (let i = 0; i < perfectSqNums.length; i++) {
38    if (n - perfectSqNums[i] >= 0) {
39      const difference = n - perfectSqNums[i];
40      // this is key - recursively solve for the next perfect square
41      // that could sum to n by traversing a graph of possible perfect square sums
42      thisPath = numSquares(paths, perfectSqNums, difference);
43
44      // compare the number of nodes required in this path
45      // to the current minimum
46      min = Math.min(min, thisPath);
47    }
48  }
49
50  min++; // increment the number of nodes seen
51  paths[n] = min; // set the difference for this number to be the min so far
52
53  return min;
54}
55
56try {
57  assert.deepEqual(howManySquares(12), 3);
58
59  console.log('PASSED: ' + 'howManySquares(12) should return 3');
60} catch (err) {
61  console.log(err);
62}
63
64try {
65  assert.deepEqual(howManySquares(1), 1);
66
67  console.log('PASSED: ' + 'howManySquares(1) should return 1');
68} catch (err) {
69  console.log(err);
70}
71
72try {
73  assert.deepEqual(howManySquares(966), 3);
74
75  console.log('PASSED: ' + 'howManySquares(966) should return 3');
76} catch (err) {
77  console.log(err);
78}