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.

```
#include<iostream>
```
```
using namespace std;
```
```
 
```
```
int minSquares(int x)
```
```
{
```

    //create an array to store results of the sub-problem

```
    int minSq[x+1];
```
```
 
```

    //minSq[i]=min. number of squares that sum upto i

```
 
```
```
    //initialization
```
```
    minSq[0]=0;
```
```
    minSq[1]=1;
```
```
 
```
```
    for(int i=2;i<=x;i++)
```
```
    {
```

        //the max. number of squares that sum upto i is equal to i

```
        minSq[i]=i;
```
```
 
```
```
        for(int j=1;j*j<=i;j++)
```
```
        {
```

            //select the minimum value for i by using already computed values

            minSq[i]=min(minSq[i],1+minSq[i-j*j]);

```
        }
```
```
    }
```
```
 
```
```
    return minSq[x];
```
```
}
```
```
 
```
```
int main()
```
```
{
```
```
    int x;
```
```
    cout<<"Enter the number "<<endl;
```
```
    cin>>x;
```
```
 
```

    cout<<"Min. number of squares that sum up to input number are "<<endl;

```
    cout<<minSquares(x);
```
```
    cout<<endl;
```
```
 
```
```
    return 0;
```
```
}
```

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.

Subscribe Now: Dynamic Programming Newsletter | Important Subjects Newsletters

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.

If you find any mistake above, kindly email to [email protected]

« Prev - Shortest Common Subsequence using Dynamic Programming

» Next - Sum of Digits Problem using Dynamic Programming

Related Posts:

Check Programming Books
Practice Design & Analysis of Algorithms MCQ
Apply for Computer Science Internship
Check Data Structure Books
Check Computer Science Books

Recommended Articles: