Minimum cost to reduce A and B to 0 using square root or divide by 2 | C ++ 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
#include <bits/stdc++.h> NEW_LINE using namespace std ; int getMinOperations ( int A , int B , int prevA , int prevB , vector < vector < int > > & dp ) { if ( A == prevA and B == prevB ) { return INT_MAX ; } if ( A == 0 and B == 0 ) { return 0 ; } if ( dp [ A ] [ B ] != -1 ) { return dp [ A ] [ B ] ; } int ans1 = getMinOperations ( A / 2 , B , A , B , dp ) ; if ( ans1 != INT_MAX ) { ans1 += 1 ; } int ans2 = getMinOperations ( A , B / 2 , A , B , dp ) ; if ( ans2 != INT_MAX ) { ans2 += 1 ; } int ans3 = getMinOperations ( sqrt ( A * B ) , sqrt ( A * B ) , A , B , dp ) ; if ( ans3 != INT_MAX ) { ans3 += 2 ; } return dp [ A ] [ B ] = min ( { ans1 , ans2 , ans3 } ) ; } int main ( ) { int A = 53 , B = 16 ; int mx = max ( A , B ) ; vector < vector < int > > dp ( mx + 1 , vector < int > ( mx + 1 , -1 ) ) ; cout << getMinOperations ( A , B , -1 , -1 , dp ) ; }