Show Buttons
Share On Facebook
Share On Twitter
Share On Google Plus
Share On Linkdin
Share On Pinterest
Share On Reddit
Share On Stumbleupon
Contact us
Hide Buttons

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

Objec­tive: Given a num­ber, Write an algo­rithm to find out min­i­mum num­bers required whose square is equal to the number.

This ques­tion has been asked in the Google Inter­view for Soft­ware Devel­oper posi­tion.This is very good prob­lem which shows the advan­tage of dynamic pro­gram­ming over recursion.

Exam­ple:

Given Number: 12

Numbers whose sum of squares are equal to 12.

12+12+12+12+12+12+12+12+12+12+12+12 = 12

22+22+22 = 12

32+12+12+12 = 12

Answer: 3 numbers (2,2,2)

Approach
Given Num­ber: N

Find the square root of a given num­ber ‘N’ and take the inte­ger part of it, say it is ‘x’

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

Exam­ple:

Given Num­ber: 12, Inte­ger part of square root of 12 is : 3. So 1,2,3 are the num­bers whose square sum can be made to 12.

Now of you notice, this prob­lem has been reduced to “Min­i­mum Coin Change Prob­lem” with some mod­i­fi­ca­tion. In “Min­i­mum Coin Change Prob­lem”, the min­i­mum num­bers of coins are required to make change of a given amount, here min­i­mum num­bers required whose square sum is equal to given number.

Recur­sive Solution:

But again we are solv­ing many sub prob­lems repeat­edly and again Dynamic Pro­gram­ming(is to rescue.

Dynamic Pro­gram­ming: 

You may also like...