Minimum cost to reduce A and B to 0 using square root or divide by 2 | Java program for the above approach ; Function to return the minimum cost of converting A and B to 0 ; If both A and B doesn 't change in  this recusrive call, then return INT_MAX  to save the code from going into  infinite loop ; Base Case ; If the answer of this recursive call is already memoised ; If A is reduced to A / 2 ; If B is reduced to B / 2 ; If both A and B is reduced to sqrt ( A * B ) ; Return the minimum of the value given by the above three subproblems , also memoize the value while returning ; Driver Code
import java . io . * ; class GFG { static int getMinOperations ( int A , int B , int prevA , int prevB , int dp [ ] [ ] ) { if ( A == prevA && B == prevB ) { return Integer . MAX_VALUE ; } if ( A == 0 && B == 0 ) { return 0 ; } if ( dp [ A ] [ B ] != - 1 ) { return dp [ A ] [ B ] ; } int ans1 = getMinOperations ( A / 2 , B , A , B , dp ) ; if ( ans1 != Integer . MAX_VALUE ) { ans1 += 1 ; } int ans2 = getMinOperations ( A , B / 2 , A , B , dp ) ; if ( ans2 != Integer . MAX_VALUE ) { ans2 += 1 ; } int ans3 = getMinOperations ( ( int ) Math . sqrt ( A * B ) , ( int ) Math . sqrt ( A * B ) , A , B , dp ) ; if ( ans3 != Integer . MAX_VALUE ) { ans3 += 2 ; } return dp [ A ] [ B ] = Math . min ( ans1 , Math . min ( ans2 , ans3 ) ) ; } public static void main ( String [ ] args ) { int A = 53 , B = 16 ; int mx = Math . max ( A , B ) ; int dp [ ] [ ] = new int [ mx + 1 ] [ mx + 1 ] ; for ( int i = 0 ; i <= mx ; i ++ ) { for ( int j = 0 ; j <= mx ; j ++ ) dp [ i ] [ j ] = - 1 ; } System . out . println ( getMinOperations ( A , B , - 1 , - 1 , dp ) ) ; } }