# Minimum Number of Squares Problem – Dynamic Programming Solutions

«
»

This is a C++ Program that Solves Minimum Number of Squares Problem using Dynamic Programming technique.

Problem Description

It is always possible to represent a number in the form of sum of squares of numbers.

For example – 15= 3^2 + 2^2 + 1^2 + 1^2
Given a number x, find the minimum number of squares whose sum equals to x.

Problem Solution

Any number can be represented in the form of sum of squares. The maximum number of squares that sum upto a number x is x(simply adding x times). Now, to find the minimum value we will calculate the results for subproblems in a bottom up fashion. Then, using these values, we will select the best result.

Expected Input and Output

Case-1:

```n=19
result=3 (3^2 + 3^2 + 1)```
Program/Source Code

Here is source code of the C++ Program to Solve Minimum Number of Squares Problem. The C++ program is successfully compiled and run on a Linux system. The program output is also shown below.

1. `#include<iostream>`
2. `using namespace std;`
3. ` `
4. `int minSquares(int x)`
5. `{`
6. `    //create an array to store results of the sub-problem`
7. `    int minSq[x+1];`
8. ` `
9. `    //minSq[i]=min. number of squares that sum upto i`
10. ` `
11. `    //initialization`
12. `    minSq[0]=0;`
13. `    minSq[1]=1;`
14. ` `
15. `    for(int i=2;i<=x;i++)`
16. `    {`
17. `        //the max. number of squares that sum upto i is equal to i`
18. `        minSq[i]=i;`
19. ` `
20. `        for(int j=1;j*j<=i;j++)`
21. `        {`
22. `            //select the minimum value for i by using already computed values`
23. `            minSq[i]=min(minSq[i],1+minSq[i-j*j]);`
24. `        }`
25. `    }`
26. ` `
27. `    return minSq[x];`
28. `}`
29. ` `
30. `int main()`
31. `{`
32. `    int x;`
33. `    cout<<"Enter the number "<<endl;`
34. `    cin>>x;`
35. ` `
36. `    cout<<"Min. number of squares that sum up to input number are "<<endl;`
37. `    cout<<minSquares(x);`
38. `    cout<<endl;`
39. ` `
40. `    return 0;`
41. `}`
Program Explanation

In the main function, we take input for the number x. We will pass this value to the function minSquares as a parameter. This function will calculate the result using bottom up DP technique and return the result which will be displayed on the standard output.

Participate in Data Structure I Certification Contest of the Month Now!
Runtime Test Cases
```
Case-1:
\$ g++ min_squares.cpp
\$ ./a.out
Enter the number
100
Min. number of squares that sum up to input number are
1```

Sanfoundry Global Education & Learning Series – Dynamic Programming Problems.
To practice all Dynamic Programming Problems, here is complete set of 100+ Problems and Solutions.