In this post, we are going to solve the 279. Perfect Squares problem of Leetcode. This problem 279. Perfect Squares is a Leetcode medium level problem. Let’s see the code, 279. Perfect Squares – Leetcode Solution.

Problem

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

Now, let’s see the code of 279. Perfect Squares – Leetcode Solution.

Perfect Squares – Leetcode Solution

We are going to provide you with the solution using both approaches:

• Memoization – Top-Down Approach
• Tabulation – Bottom-Up Approach

279. Perfect Squares – Solution in Java

This is the code of the Memoization or the Top-Down Approach for the problem perfect square in Java Programming Language.

class Solution {
    
 public int solveMemo(int n,int[] dp){
        if(n == 0)return 0;
        if(dp[n] != Integer.MAX_VALUE)return dp[n];
        int ans = Integer.MAX_VALUE;
        for(int i=1; i*i <= n ;i++){
            ans = Math.min(ans,solveMemo(n-i*i,dp)+1);
        }
        dp[n] = ans;
        return dp[n];
    }

public int numSquares(int n) {
        int[] dp = new int[n+1];
        Arrays.fill(dp,Integer.MAX_VALUE);
        return solveMemo(n,dp);
    }
}

Now, let’s see the code of the Tabulation or the Bottom-Up Approach for the problem perfect square in Java Programming Language.

class Solution {

    public int solveTab(int n){
        int[] dp = new int[n+1];
        Arrays.fill(dp,Integer.MAX_VALUE);
        dp[0] = 0;
        dp[1] = 1;
    for(int idx=2;idx<=n;idx++)
        for(int i=1;i*i<=idx;i++){
            dp[idx] = Math.min(dp[idx],dp[idx-i*i]+1); 
        }
        return dp[n];
    }
    
    public int numSquares(int n) {
        return solveTab(n);
    }
}

279. Perfect Squares – Solution in C++

This is the code of the Memoization or the Top-Down Approach for the problem perfect square in C++ Programming Language.

class Solution {
public:
    int solveMemo(int n,vector<int>& dp){
        if(n == 0)return 0;
        if(dp[n] != INT_MAX)return dp[n];
        int ans = INT_MAX;
        for(int i=1; i*i <= n ;i++){
            ans = min(ans,solveMemo(n-i*i,dp)+1);
        }
        dp[n] = ans;
        return dp[n];
    }
    
    
    int numSquares(int n) {
        vector<int> dp(n+1,INT_MAX);
        return solveMemo(n,dp);
    }
};

Now, let’s see the code of the Tabulation or the Bottom-Up Approach for the problem perfect square in C++ Programming Language.

class Solution {
public:
    int solveTab(int n){
        vector<int> dp(n+1,INT_MAX);
        dp[0] = 0;
        dp[1] = 1;
        for(int idx=2;idx<=n;idx++)
            for(int i=1;i*i<=idx;i++){
                dp[idx] = min(dp[idx],dp[idx-i*i]+1); 
            }
        return dp[n];
    }
    int numSquares(int n) {
        return solveTab(n);
    }
};

279. Perfect Squares – Solution in Python

class Solution:
    def numSquares(self, n: int) -> int:
        dp = [n] * (n + 1)
        dp[0] = 0
        
        for target in range(1, n + 1):
            for s in range(1, target + 1):
                square = s * s
                if square > target:
                    break
                if 1 + dp[target - square] < dp[target]:
                    dp[target] = 1 + dp[target - square]
        return dp[n]

Note: This problem 279. Perfect Squares is generated by Leetcode but the solution is provided by CodingBroz. This tutorial is only for Educational and Learning purpose.