# Perfect Squares – Leetcode Solution

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.