Convert 1 into X in min steps by multiplying with 2 or 3 or by adding 1 | Function to print the Minimum number of operations required to convert 1 into X by using three given operations ; Initialize a DP array to store min operations for sub - problems ; Base Condition : No operation required when N is 1 ; Multiply the number by 2 ; Multiply the number by 3 ; Add 1 to the number . ; Print the minimum operations ; Initialize a list to store the sequence ; Backtrack to find the sequence ; If add by 1 ; If multiply by 2 ; If multiply by 3 ; Print the sequence of operation ; Given number X ; Function Call
def printMinOperations ( N ) : NEW_LINE INDENT dp = [ N ] * ( N + 1 ) NEW_LINE dp [ 1 ] = 0 NEW_LINE for i in range ( 2 , N + 1 ) : NEW_LINE INDENT if ( i % 2 == 0 and dp [ i ] > dp [ i // 2 ] + 1 ) : NEW_LINE INDENT dp [ i ] = dp [ i // 2 ] + 1 NEW_LINE DEDENT if ( i % 3 == 0 and dp [ i ] > dp [ i // 3 ] + 1 ) : NEW_LINE INDENT dp [ i ] = dp [ i // 3 ] + 1 NEW_LINE DEDENT if ( dp [ i ] > dp [ i - 1 ] + 1 ) : NEW_LINE INDENT dp [ i ] = dp [ i - 1 ] + 1 NEW_LINE DEDENT DEDENT print ( dp [ N ] , end = " " ) NEW_LINE seq = [ ] NEW_LINE while ( N > 1 ) : NEW_LINE INDENT seq . append ( N ) NEW_LINE if dp [ N - 1 ] == dp [ N ] - 1 : NEW_LINE INDENT N = N - 1 NEW_LINE DEDENT elif N % 2 == 0 and dp [ N // 2 ] == dp [ N ] - 1 : NEW_LINE INDENT N = N // 2 NEW_LINE DEDENT else : NEW_LINE INDENT N = N // 3 NEW_LINE DEDENT DEDENT seq . append ( 1 ) NEW_LINE for i in reversed ( seq ) : NEW_LINE INDENT print ( i , end = " ▁ " ) NEW_LINE DEDENT DEDENT X = 96234 NEW_LINE printMinOperations ( X ) NEW_LINE