Minimum number of squares whose sum equals to given number n
A number can always be represented as a sum of squares of other numbers. Note that 1 is a square and we can always break a number as (1*1 + 1*1 + 1*1 + …). Given a number n, find the minimum number of squares that sum to X.
Examples:
Input: n = 100 Output: 1 100 can be written as 10^{2}. Note that 100 can also be written as 5^{2} + 5^{2} + 5^{2} + 5^{2}, but this representation requires 4 squares. Input: n = 6 Output: 3
The idea is simple, we start from 1 and go till a number whose square is smaller than or equals to n. For every number x, we recur for nx. Below is the recursive formula.
If n <= 3, then return n Else minSquares(n) = min {1 + minSquares(n  x*x)} where x >= 1 and x*x <= n
Below is a simple recursive solution based on above recursive formula.
 C++

// A naive recursive C++ program to find minimum
// number of squares whose sum is equal to a given number
#include<bits/stdc++.h>
using
namespace
std;
// Returns count of minimum squares that sum to n
int
getMinSquares(unsigned
int
n)
{
// base cases
if
(n <= 3)
return
n;
// getMinSquares rest of the table using recursive
// formula
int
res = n;
// Maximum squares required is n (1*1 + 1*1 + ..)
// Go through all smaller numbers
// to recursively find minimum
for
(
int
x = 1; x <= n; x++)
{
int
temp = x*x;
if
(temp > n)
break
;
else
res = min(res, 1+getMinSquares(n  temp));
}
return
res;
}
// Driver program
int
main()
{
cout << getMinSquares(6);
return
0;
}
Output:
3
The time complexity of above solution is exponential. If we draw the complete recursion tree, we can observer that many subproblems are solved again and again. For example, when we start from n = 6, we can reach 4 by subtracting one 2 times and by subtracting 2 one times. So the subproblem for 4 is called twice.
Since same suproblems are called again, this problem has Overlapping Subprolems property. So min square sum problem has both properties of a dynamic programming problem. Like other typical Dynamic Programming(DP) problems, recomputations of same subproblems can be avoided by constructing a temporary array table[][] in bottom up manner. Below is Dynamic Programming based solution
 C++

// A dynamic programming based C++ program to find minimum
// number of squares whose sum is equal to a given number
#include<bits/stdc++.h>
using
namespace
std;
// Returns count of minimum squares that sum to n
int
getMinSquares(
int
n)
{
// Create a dynamic programming table
// to store sq
int
*dp =
new
int
[n+1];
// getMinSquares table for base case entries
dp[0] = 0;
dp[1] = 1;
dp[2] = 2;
dp[3] = 3;
// getMinSquares rest of the table using recursive
// formula
for
(
int
i = 4; i <= n; i++)
{
// max value is i as i can always be represented
// as 1*1 + 1*1 + ...
dp[i] = i;
// Go through all smaller numbers to
// to recursively find minimum
for
(
int
x = 1; x <= i; x++) {
int
temp = x*x;
if
(temp > i)
break
;
else
dp[i] = min(dp[i], 1+dp[itemp]);
}
}
// Store result and free dp[]
int
res = dp[n];
delete
[] dp;
return
res;
}
// Driver program
int
main()
{
cout << getMinSquares(6);
return
0;
}
Output:
3
Disclaimer: This does not belong to TechCodeBit, its an article taken from the below
source and credits.
source and credits: http://www.geeksforgeeks.org
We have built the accelerating growthoriented website for budding engineers and aspiring job holders of technology companies such as Google, Facebook, and Amazon
If you would like to study our free courses you can join us at
http://www.techcodebit.com. #techcodebit #google #microsoft #facebook #interview portal #jobplacements
#technicalguide