This post is completed by 1 user

  • 0
 Add to List
Hard

173. Minimize Square Sums: Fewest Perfect Squares to Reach a Target (Dynamic Programming)

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

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

Example:

Given Number: 12

Numbers whose sum of squares is 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 that can be used, whose square sum is equal to N.

Example:

Given Number: 12, the Integer part of the square root of 12 is : 3. So 1,2,3 are the numbers that square sum can be made to 12. And those numbers are (2, 2, 2)

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 the change of a given amount, here minimum numbers are required whose square sum is equal to the given number.

Recursive Solution:

 

But again we are solving many sub-problems repeatedly and again Dynamic Programming is to rescue. We will solve this problem in a bottom-up manner. See the code below for a better understanding.

 
3

Related Problems: