This problem is from careercup. http://www.careercup.com/question?id=5725584103571456
Given a number “n”, find the least number of perfecet square numbers sum needed to get “n”.
Exmaple:
n=12, return 3 (4+4+4)=(2^2+2^2+2^2) NOT (3^2+1+1^2+1^2)
n=6, return 3(4+1+1)=(2^2+1^2+1^2)
At first sight, I thought this could be resolved by greedy method:
round(sqrt(12))=3, remainder=3;
round(sqrt(3))=1, remainder=2;
round(sqrt(2))=1, remainder=1;
But this won’t give out a optimized answer.
This problem is actually a dynamic programming problem. It is very similar to Fibonacci. Let’s assume table[i] stores the answer for least perfect square. Let’s think about how to get table[12].
12 = 11+1^2
12 = 8+2^2
12 = 3+ 3^2
In this way, we know that table[12]=min{table[3]+1, table[8]+1, table[11]+1}
We can compute table[3], table[8], table[11] accordingly like this. We just need to find the numbers before each one, which add a power number and can reach it. To understandy the solution, I wrote below code. It helps to understand. But it is not efficient.
/** Inefficient version */
static int leastPerfectSquare1(int n){
if(n==1){
return 1;
}
else if(n==0){
return 0;
}
int maxSquare = (int)Math.sqrt(n);
int result = n;
for(int i=1;i<=maxSquare; i++){
int tmpResult = leastPerfectSquare1(n - (int) Math.pow(i, 2)) + 1;
result = (tmpResult < result) ? tmpResult : result;
}
return result;
}
Below version stores the sub solutions.
/** Recursion storing sub solutions **/
static int leastPerfectSquare2(int n){
int[] storedResult = new int[n + 1];
storedResult[1] = 1;
return leastPerfectSquare2Helper(n, storedResult);
}
static int leastPerfectSquare2Helper(int n, int[] storedResult){
if(n==0){
return 0;
}
int maxSquare = (int)Math.sqrt(n);
int result = n;
for(int i=1;i<=maxSquare; i++){
int power = (int)Math.pow(i, 2);
int tmpResult = 0;
if(storedResult[n - power]!=0){
tmpResult = storedResult[n - power] + 1;
}
else {
tmpResult = leastPerfectSquare2Helper(n - power, storedResult) + 1;
}
result = (tmpResult < result) ? tmpResult : result;
}
storedResult[n] = result;
return result;
}
Below version is the effective one compared to above 2 versions. It only uese loop, takes O(n) time. It loop all the potentional squre number, and see what position of number can use it to compute the next one.(hard to explain, reading the code would be helpful.)
/** Non-recursion solution **/
static int leastPerfectSquare3(int n){
int[] table = new int[n+1];
for(int i=0;iint maxSquare = (int) Math.sqrt(n);
for(int i=2; i<=maxSquare; i++){
int power = (int) Math.pow(i, 2);
int boundary = n - power;
for(int j=0;j<=boundary; j++){
if(table[j] + 1 < table[j+power] ){
table[j+power] = table[j] + 1;
}
}
}
return table[n];
}