One Pager Cheat Sheet
- Perfect squares are numbers that result from squaring a whole number and can be used to find the fewest number of perfect squares that sum to a given number n, subject to the constraints of
n
being a nonzero positive integer less than or equal to10000
, and the expected time/space complexity beingO(n*sqrt(n))
/O(n)
, respectively. - A number is a perfect square when its square root is a whole number, such as the 1st to 10th
perfect squares
, which are1, 4, 9, 16, 25, 36, 49, 64, 81, 100
. - We need to iterate through all possible numbers and perform a logical step at each step to find the least number of perfect squares that sum up to a given number.
- The
for
loop will check each number from 1 up to the given number to see if it is a perfect square andcount
is incremented by 1 for each perfect square found. - We can reduce our brute force solution to be more efficient by considering only perfect squares that are less than our target number, and iterating through these to sum them up to the target.
- We can optimize the time complexity of finding the minimum number of perfect squares needed to add up to a certain sum by turning it into a shortest path problem, constructing a
graph
and memo-izing the calculations with ahash
or anarray
.
This is our final solution.
To visualize the solution and step through the below code, click Visualize the Solution on the right-side menu or the VISUALIZE button in Interactive Mode.
xxxxxxxxxx
78
}
var assert = require('assert');
​
function howManySquares(n) {
let perfectSqNumsLength = 1;
while (perfectSqNumsLength * perfectSqNumsLength < n) {
perfectSqNumsLength++;
}
​
if (perfectSqNumsLength * perfectSqNumsLength > n) {
perfectSqNumsLength--;
}
​
const perfectSqNums = [];
​
// Fill the array backwards so we get the numbers to work with
for (let i = perfectSqNumsLength - 1; i >= 0; i--) {
perfectSqNums[perfectSqNumsLength - i - 1] = (i + 1) * (i + 1);
}
​
// instantiate a hashmap of possible paths
const paths = {};
paths[1] = 1; // 1 = 1
paths[0] = 0; // 0 means you need 0 numbers to get 0
​
return numSquares(paths, perfectSqNums, n);
}
​
function numSquares(paths, perfectSqNums, n) {
if (paths.hasOwnProperty(n)) {
// we already knew the paths to add up to n.
return paths[n];
}
OUTPUT
:001 > Cmd/Ctrl-Enter to run, Cmd/Ctrl-/ to comment
You're doing a wonderful job. Keep going!
If you had any problems with this tutorial, check out the main forum thread here.