You have to find the minimum number of squares that sum to N.
You can always represent a number as a sum of squares of other numbers.
In worst case N can be represented as (1*1) + (1*1) + (1*1)..... N times.
For example, N=9. As 9= 3 2 , it can be represented by a minimum of 1 square.
Also, if N=10, then since 10=1 2 +3 2 , therefore it can be represented by a sum of
minimum 2 squares (i.e. of 1 and 3).
Let's take one last example, if N=7, then it can be written as 7= 1 2 +1 2 +1 2 +2 2 . Hence it
can be represented as a sum of minimum 4 squares.
Approach
We understand the approach of this problem by taking N=11. Since 11=1 2 +1 2 +3 2 ,
therefore, it can be represented as a sum of minimum 3 squares.
STORAGE & MEANING:
To proceed with the approach, we make an array for DP of size N+1=12 from indices
0 to 11.
At an index, say i, we store the minimum number of squares required to form that
number 'i' .
DIRECTION:
We solve this array from the lowest index to the highest index (from left to right).
SOLVE & TRAVERSE:
Reader, we already know that the minimum squares required to get a sum of
0 is 0. Also, 1 can only be represented as a square of 1. So we store these
values at the respective indices.
Now we need to figure out the answer for N=2.
For that, we use the concept shown in following figure.
In this figure, we are given 3 ways to reach from source to destination, x, y and z.
The minimum steps required to reach the destination is the sum of minimum
out of x, y and z distances and the distance corresponding to that minimum
from source to a or b or c.
We use the same approach for this problem.
As shown in Figure 4, from N=2, we subtract the square of the minimum
value possible, 1. This leads us to N=1. At N=1, the minimum squares required
=1.
Hence, for N=2, the minimum squares required are a sum of minimum
squares required at N=1 and the 1 2 you had originally moved back i.e. 1 2
+1 2 .Hence, the minimum squares required here are 2.
Now let's move on to N=3.
Again, we subtract the square of minimum value possible, 1 from the N=3 and
reach N=2.
For N=3, the number of minimum squares required is the sum of minimum
squares required for N=2 and the square of 1 we had originally subtracted i.e.
1 2 +1 2 +1 2 . Hence, the minimum squares required here are 3.
Here, we could not have subtracted the square of the next minimum value 2.
Because of doing so, we would have to move back 2 2 steps from N=3 and
would have reached N=-1 which doesn't exist.
Reader, we know that you might not have understood this traversal for the
initial indices but you soon will.
We reach N=4.
METHOD 1 : First, we try to subtract the square of minimum value possible, 1
from the N=4 and reach N=3.
Hence, for N=4, the minimum squares required are the sum of minimum
squares required for N=3 and the square of 1 we had originally subtracted
which is equal to 1 2 +1 2 +1 2 +1 2 . Hence, the minimum squares required here are
4.
METHOD 2: But, it is also possible to subtract N=4 by the square of next
minimum value, 2. On doing so, we reach N= 4- 2 2 =0. For N=0, the minimum
squares required are 0.
Hence, the other way of obtaining the minimum number of squares for N=4
is the sum of minimum squares required for N=0 and the square of 2 we had
originally subtracted which is equal to 0+2 2 . Hence, the minimum squares
required here is 1.
As shown in previous figure, we choose the minimum answer out of Method 1 and
Method 2. Hence, we choose method 2 where only 1 square is required.
The above process is repeated for all the numbers till N=11. The minimum
squares required for N=11 is stored at the index 11 of the array which is our
final answer.
We want you to practice solving it for the rest of the numbers and then tally
the result with below figure.
You can also watch the solution video if you get stuck
somewhere.
Dear Reader, if you have paid close attention to the approach of this problem, you will find the following code to be pretty straightforward.
import java.io.*;
import java.util.*;
public class Main {
public static int solution(int n){
int[]dp=new int[n+1];
dp[0]=0;
dp[1]=1;
for(int i=2;i<=n;i++){
int min=Integer.MAX_VALUE;
for(int j=1;j*j<=i;j++){
int rem=i-j*j;
if(dp[rem]< min){
min=dp[rem];
}
}
dp[i]=min+1;
}
return dp[n];
}
public static void main(String[] args) {
Scanner scn = new Scanner(System.in);
int n = scn.nextInt();
System.out.println(solution(n));
}
}
java;
true";
Analysis
Time Complexity O(n^2)
Space Complexity O(n)
We come to the end of this article here. We hope you were able to understand it. If
you still have any doubts, you should watch the solution video too.
