// 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;
}