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


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;
  4. int minSquares(int x)
  5. {
  6.     //create an array to store results of the sub-problem
  7.     int minSq[x+1];
  9.     //minSq[i]=min. number of squares that sum upto i
  11.     //initialization
  12.     minSq[0]=0;
  13.     minSq[1]=1;
  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;
  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.     }
  27.     return minSq[x];
  28. }
  30. int main()
  31. {
  32.     int x;
  33.     cout<<"Enter the number "<<endl;
  34.     cin>>x;
  36.     cout<<"Min. number of squares that sum up to input number are "<<endl;
  37.     cout<<minSquares(x);
  38.     cout<<endl;
  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
$ g++ min_squares.cpp
$ ./a.out
Enter the number 
Min. number of squares that sum up to input number are 

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


Subscribe to our Newsletters (Subject-wise). Participate in the Sanfoundry Certification contest to get free Certificate of Merit. Join our social networks below and stay updated with latest contests, videos, internships and jobs!

Youtube | Telegram | LinkedIn | Instagram | Facebook | Twitter | Pinterest
Manish Bhojasia - Founder & CTO at Sanfoundry
Manish Bhojasia, a technology veteran with 20+ years @ Cisco & Wipro, is Founder and CTO at Sanfoundry. He lives in Bangalore, and focuses on development of Linux Kernel, SAN Technologies, Advanced C, Data Structures & Alogrithms. Stay connected with him at LinkedIn.

Subscribe to his free Masterclasses at Youtube & discussions at Telegram SanfoundryClasses.