Skip to main content

Perfect Squares

Problem statement​

Given an integer n, return the least number of perfect square numbers that sum to n.

A perfect square is an integer that is the square of an integer; in other words, it is the product of some integer with itself. For example, 1, 4, 9, and 16 are perfect squares while 3 and 11 are not.

Example 1:

Input: n = 12Output: 3Explanation: 12 = 4 + 4 + 4.

Example 2:

Input: n = 13Output: 2Explanation: 13 = 4 + 9.

Constraints:

  • 1 <= n <= 104

My solution​

/**
 * @param {number} n
 * @return {number}
 */
var numSquares = function(n) {
    const memo = Array.from({
        length: n + 1
    }, () => Number.MAX_SAFE_INTEGER)
    memo[0] = 0
    
    for (let i = 1; i <= n; i++) {
        for (let j = 1; j * j <= i; j++) {
            memo[i] = Math.min(memo[i], memo[i - j * j] + 1)
        }
    }
    
    // console.log(memo)
    return memo[n]
};