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
function printMinOperations ( N ) { var dp = Array ( N + 1 ) for ( var i = 0 ; i < N + 1 ; i ++ ) dp [ i ] = N ; dp [ 1 ] = 0 ; for ( var i = 2 ; i < N + 1 ; i ++ ) { if ( i % 2 == 0 && dp [ i ] > dp [ i / 2 ] + 1 ) dp [ i ] = dp [ i / 2 ] + 1 ; if ( i % 3 == 0 && dp [ i ] > dp [ i / 3 ] + 1 ) dp [ i ] = dp [ i / 3 ] + 1 ; if ( dp [ i ] > dp [ i - 1 ] + 1 ) dp [ i ] = dp [ i - 1 ] + 1 ; } document . write ( dp [ N ] + " " ) ; var seq = [ ] ; while ( N > 1 ) { seq . push ( N ) ; if ( dp [ N - 1 ] == dp [ N ] - 1 ) N = N - 1 ; else if ( N % 2 == 0 && dp [ N / 2 ] == dp [ N ] - 1 ) N = N / 2 ; else N = N / 3 ; } seq . push ( 1 ) ; for ( var i = seq . length - 1 ; i >= 0 ; i -- ) document . write ( seq [ i ] + " " ) ; document . write ( " " ) ; } var X = 96234 ; printMinOperations ( X ) ;