// dp
const numSquares = function (n) {
let res = [0, 1, 2, 3],
ii;
for (let i = 4; i <= n; ++i) {
res[i] = Number.MAX_SAFE_INTEGER;
}
for (let i = 4; i <= n; ++i) {
ii = 1;
while (i - Math.pow(ii, 2) >= 0) {
res[i] = Math.min(res[i - Math.pow(ii, 2)] + 1, res[i]);
++ii;
}
}
return res[n];
};
// math
const numSquares = function (n) {
if (isSquare(n)) {
return 1;
}
// The result is 4 if and only if n can be written in the
// form of 4^k*(8*m + 7). Please refer to
// Legendre's three-square theorem.
while ((n & 3) == 0) // n%4 == 0
{
n >>= 2;
}
if ((n & 7) == 7) // n%8 == 7
{
return 4;
}
// Check whether 2 is the result.
let sqrt_n = parseInt(Math.sqrt(n));
for (let i = 1; i <= sqrt_n; i++) {
if (isSquare(n - i * i)) {
return 2;
}
}
return 3;
};
const isSquare = function (n) {
return parseInt(Math.sqrt(n)) * parseInt(Math.sqrt(n)) === n;
}