Dynamic Programming - Minimum Numbers are Required Whose Square Sum is Equal To a Given Number | Algorithms

Dynamic Programming - Minimum Numbers are Required Whose Square Sum is Equal To a Given Number | Algorithms
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.

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)

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.

DP solution:

public int solveUsingDP(int n, int options) {


int MN[] = new int[n+1]; // Minimum numbers required whose sum is = n


MN[0] = 0; // if number is 0 the answer is 0.


int[] NUM = new int[options+1];


// solve in bottom up manner


for (int number = 1; number <= n; number++) {


// reset the NUM[] for new i


for (int j = 0; j <= options; j++) {


NUM[j] = 0;


}


// now try every option one by one and fill the solution in NUM[]


for (int j = 1; j <= options; j++) {


// check the criteria


if (j * j <= number) {


// select the number, add 1 to the solution of number-j*j


NUM[j] = MN[number - j * j] + 1;


}


}




//Now choose the optimal solution from NUM[]


MN[number]=-1;


for(int j=1;j<NUM.length;j++){


if(NUM[j]>0 && (MN[number]==-1 || MN[number]>NUM[j])){


MN[number]=NUM[j];


}


}


}


return MN[n];


}

Recur­sive Solution:

public void solve(int n) {


int options = (int) Math.sqrt(n);


//solve using recursion


System.out.println(solveRecursively(n, options));


}


 


public int solveRecursively(int n, int options) {


if (n <= 0) {


return 0;


}


int min = solveRecursively(n - 1 * 1, options);


for (int i = 2; i <= options; i++) {


if (n >= i * i) {


min = Math.min(min, solveRecursively(n - i * i, options));


}


}


return min + 1;


}

Read full article from Dynamic Programming - Minimum Numbers are Required Whose Square Sum is Equal To a Given Number | Algorithms