(1)Best way.94%
This one uses Lagrange's four-square theorem.
According to it, every integer is a sum of at most 4 perfect square numbers. Therefore the result should be one of 1,2,3,4.
class Solution {
public:
int numSquares(int n) {
while (n % 4 == 0) n /= 4;//no effect on result, but simplified calculate.
if (n % 8 == 7) return 4;//by theorem.
for (int a = 0; a * a <= n; ++a) {
int b = sqrt(n - a * a);
if (a * a + b * b == n)
{
return !!a + !!b;//!!is to find out if a,b is 0 or 1.
}
}
return 3;
}
};
(2)DP:
Actually the 2 ways below use the same method. The only difference is they use different containers. One uses hmap, another one uses vector. But the result of time has a great difference.I do not know why, and hope someone can answer.
class Solution {
public:
int numSquares(int n) {
unordered_map<int,int> hmap;
if(n==1)
return 1;
hmap[0]=0;
for(int m=1;m<=n;m++)
{
int minval=INT_MAX;
for(int j=1;j*j<=m;j++)
{
hmap[j*j]=1;
minval=min(minval,hmap[j*j]+hmap[m-j*j]);
}
hmap[m]=minval;
}
return hmap[n];
}
};
This one is not good. Time Limit Exceeded, time 5673ms.
Let's see another one.
class Solution {
public:
int numSquares(int n) {
vector<int> hmap(1,0);
for(int m=1;m<=n;m++)
{
int minval=INT_MAX;
for(int j=1;j*j<=m;j++)
{
minval=min(minval,1+hmap[m-j*j]);
}
hmap.push_back(minval);
}
return hmap.back();
}
};
This one is better. 46% and runing time is 320ms.