**Objective: **Given a number, Write an algorithm to find out minimum numbers required whose square is equal to the number.

This question has been asked in the *Google Interview* for *Software Developer position*.This is very good problem which shows the advantage of dynamic programming over recursion.

**Example:**

Given Number: 12 Numbers whose sum of squares are equal to 12. 1^{2}+1^{2}+1^{2}+1^{2}+1^{2}+1^{2}+1^{2}+1^{2}+1^{2}+1^{2}+1^{2}+1^{2}= 12 2^{2}+2^{2}+2^{2}= 12 3^{2}+1^{2}+1^{2}+1^{2}= 12 Answer: 3 numbers (2,2,2)

**Approach**

*Given Number: N*

*Find the square root of a given number ‘N’ and take the integer part of it, say it is ‘x’*

*Now numbers from 1 to x are the options which can be used, whose square sum is equal to N.*

**Example****: **

*Given Number: 12, Integer part of square root of 12 is : 3. So 1,2,3 are the numbers whose square sum can be made to 12.*

Now of you notice, this problem has been reduced to “* Minimum Coin Change Problem*” with some modification. In “

*Minimum Coin Change Problem*“, the minimum numbers of coins are required to make change of a given amount, here minimum numbers required whose square sum is equal to given number.

**Recursive Solution:**

This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.

Learn more about bidirectional Unicode characters

public class SmallSquare { | |

public void solve(int n) { | |

int options = (int) Math.sqrt(n); | |

//solve using recursion | |

System.out.println("Minimum Numbers are Required Whose Square Sum is Equal To a "+n+": " + solveRecursively(n, options)); | |

} | |

public int solveRecursively(int n, int options) { | |

if (n <= 0) { | |

return 0; | |

} | |

int min = solveRecursively(n – 1 * 1, options); | |

for (int i = 2; i <= options; i++) { | |

if (n >= i * i) { | |

min = Math.min(min, solveRecursively(n – i * i, options)); | |

} | |

} | |

return min + 1; | |

} | |

public static void main(String[] args) { | |

int N = 12; | |

SmallSquare s = new SmallSquare(); | |

s.solve(N); | |

} | |

} |

*But again we are solving many sub problems repeatedly and again Dynamic Programming(is to rescue.*

**Dynamic Programming:**

This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.

Learn more about bidirectional Unicode characters

public class SmallSquare { | |

public void solve(int n) { | |

int options = (int) Math.sqrt(n); | |

//solve using Dynamic programming | |

System.out.println(solveUsingDP(n, options)); | |

} | |

public int solveUsingDP(int n, int options) { | |

int MN[] = new int[n+1]; // Minimum numbers required whose sum is = n | |

MN[0] = 0; // if number is 0 the answer is 0. | |

int[] NUM = new int[options+1]; | |

// solve in bottom up manner | |

for (int number = 1; number <= n; number++) { | |

// reset the NUM[] for new i | |

for (int j = 0; j <= options; j++) { | |

NUM[j] = 0; | |

} | |

// now try every option one by one and fill the solution in NUM[] | |

for (int j = 1; j <= options; j++) { | |

// check the criteria | |

if (j * j <= number) { | |

// select the number, add 1 to the solution of number-j*j | |

NUM[j] = MN[number – j * j] + 1; | |

} | |

} | |

//Now choose the optimal solution from NUM[] | |

MN[number]=–1; | |

for(int j=1;j<NUM.length;j++){ | |

if(NUM[j]>0 && (MN[number]==–1 || MN[number]>NUM[j])){ | |

MN[number]=NUM[j]; | |

} | |

} | |

} | |

return MN[n]; | |

} | |

public static void main(String[] args) { | |

int N = 12; | |

SmallSquare s = new SmallSquare(); | |

s.solve(N); | |

} | |

} |

3