by SJ · July 3, 2015 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. 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 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.
Read full article from Dynamic Programming - Minimum Numbers are Required Whose Square Sum is Equal To a Given Number | Algorithms
No comments:
Post a Comment