279. Perfect Squares

Perfect Squares

Problem Description

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 = 12
Output: 3
Explanation: 12 = 4 + 4 + 4.

Example 2:

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

 

Constraints:

• 1 <= n <= 104

Approach) Short DP 

var numSquares = function(n) {
    var dp=[0];

    for (var i=1;i<=n;i++)
        for (var j=Math.sqrt(i)|0; j>=1 ;j--)
            dp[i]=Math.min(dp[i] || n, dp[i-j*j]+1)


    return dp[n]
};

Approach) Math Number Theory

// Math number theory 100ms 96.69% fast
const numSquares = (n) => {
    while (n % 4 == 0) {
        n /= 4;
    }
    if (n % 8 == 7) return 4;
    for (let a = 0; a * a <= n; a++) {
        let b = Math.floor(Math.sqrt(n - a * a));
        if (a * a + b * b == n) return !!a + !!b;
    }
    return 3;
};

Approach) Greedy + Breadth-First Search

/**
 * @param {number} n
 * @return {number}
 */
var numSquares = function(n) {

    let squares = new Set();
    for (let i = 1; i * i <= n; ++i) squares.add(i * i);
    let queue = new Set();
    queue.add(n);

    let level = 0;
    while (queue.size > 0) {
      level += 1;
      let nextQueue = new Set();

      for (let remainder of queue) {
        for (let square of squares) {
          if (remainder === square)
            return level;
          else if (remainder < square)
            break;
          else
            nextQueue.add(remainder - square);
        }
      }
      queue = nextQueue;
    }
    return level;
};

Approach) Recursion - with memo

/**
 * @param {number} n
 * @return {number}
 */
var numSquares = function(n) {
    if(n < 1) {
        return 0;
    }
    
    let range = Math.floor(Math.sqrt(n));
    
    let squares = [];
    
    for (let i = 1; i <= range; i++ ) {
        squares.push(i*i);
    }
    
    let dp = new Array(squares.length + 1);
    
    for (let i = 0; i <= squares.length ; i++) {
        dp[i] = new Array(n+1).fill(-1);
    }
    
    return isSum(squares, n, squares.length, dp);

};

const isSum = (squares, j, i, dp) => {
    if (j === 0) {
        return 0;
    }
    
    if (j < 0 || i < 1) {
        return Number.MAX_SAFE_INTEGER;
    }
    
    if(dp[i][j] !== -1) {
        return dp[i][j];
    }
    
    if(squares[i-1] <= j) {
        return dp[i][j] = Math.min( 1 + isSum(squares, j - squares[i-1], i, dp), isSum(squares, j, i-1, dp));
    } else {
        return dp[i][j] = isSum(squares, j, i-1, dp);
    }
}

Approach) Unbounded Knapsack

/**
 * @param {number} n
 * @return {number}
 */
var numSquares = function(n) {
    if(n < 1) {
        return 0;
    }
    
    let range = Math.floor(Math.sqrt(n));
    
    let squares = [];
    
    for (let i = 1; i <= range; i++ ) {
        squares.push(i*i);
    }
    
    let dp = new Array(squares.length + 1);
    
    for (let i = 0; i < 2; i++) {
        dp[i] = new Array(n+1).fill(Number.MAX_SAFE_INTEGER);
    }
    
    let flag = 1;
    
    for (let i = 0; i < dp.length; i++) {
        for (let j = 0; j <= n; j++) {
            if (i === 0) {
                dp[flag][j] = Number.MAX_SAFE_INTEGER;
            } else if (j === 0) {
                dp[flag][j] = 0;
            } else {
                if (squares[i-1] <= j) {
                    dp[flag][j] = Math.min(1 + dp[flag][j-squares[i-1]], dp[flag^1][j]); 
                } else {
                    dp[flag][j] = dp[flag^1][j];
                }
            }
        }
        flag ^= 1;
    }
    return dp[flag^1][n];
};




Conclusion

That’s all folks! In this post, we solved LeetCode problem 279. Perfect Squares

I hope you have enjoyed this post. Feel free to share your thoughts on this.

You can find the complete source code on my GitHub repository. If you like what you learn. feel free to fork 🔪 and star ⭐ it.

In this blog, I have tried to collect & present the most important points to consider when improving Data structure and logic, feel free to add, edit, comment, or ask. For more information please reach me here
Happy coding!