**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:**

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

**Dynamic Programming:*** *

__________________________________________________

**Top Companies Interview Questions..-**

If you find anything incorrect or you feel that there is any better approach to solve the above problem, please write comment.

__________________________________________________

### Like this:

Like Loading...

*Related*