# Dynamic Programming – Minimum Numbers are Required Whose Square Sum is Equal To a Given Number

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

3