Minimum cost to reduce A and B to 0 using square root or divide by 2 | Python 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 math as Math NEW_LINE def getMinOperations ( A , B , prevA , prevB , dp ) : NEW_LINE INDENT if ( A == prevA and B == prevB ) : NEW_LINE INDENT return 10 ** 9 ; NEW_LINE DEDENT if ( A == 0 and B == 0 ) : NEW_LINE INDENT return 0 ; NEW_LINE DEDENT if ( dp [ A ] [ B ] != - 1 ) : NEW_LINE INDENT return dp [ A ] [ B ] ; NEW_LINE DEDENT ans1 = getMinOperations ( A // 2 , B , A , B , dp ) ; NEW_LINE if ( ans1 != 10 ** 9 ) : NEW_LINE INDENT ans1 += 1 ; NEW_LINE DEDENT ans2 = getMinOperations ( A , B // 2 , A , B , dp ) ; NEW_LINE if ( ans2 != 10 ** 9 ) : NEW_LINE INDENT ans2 += 1 ; NEW_LINE DEDENT ans3 = getMinOperations ( Math . floor ( Math . sqrt ( A * B ) ) , Math . floor ( Math . sqrt ( A * B ) ) , A , B , dp ) ; NEW_LINE if ( ans3 != 10 ** 9 ) : NEW_LINE INDENT ans3 += 2 ; NEW_LINE DEDENT dp [ A ] [ B ] = min ( ans1 , min ( ans2 , ans3 ) ) NEW_LINE return dp [ A ] [ B ] ; NEW_LINE DEDENT A = 53 NEW_LINE B = 16 NEW_LINE mx = max ( A , B ) ; NEW_LINE dp = [ [ - 1 for i in range ( mx + 1 ) ] for i in range ( mx + 1 ) ] NEW_LINE print ( getMinOperations ( A , B , - 1 , - 1 , dp ) ) ; NEW_LINE