Minimum Steps to obtain N from 1 by the given operations | Python3 program to implement the above approach ; Base Case ; Recursive Call for n - 1 ; Check if n is divisible by 2 ; Check if n is divisible by 3 ; Returns a tuple ( a , b ) , where a : Minimum steps to obtain x from 1 b : Previous number ; Function that find the optimal solution ; Print the length ; Exit condition for loop = - 1 when n has reached 1 ; Return the sequence in reverse order ; Given N ; Function Call
def find_sequence ( n ) : NEW_LINE INDENT if n == 1 : NEW_LINE INDENT return 1 , - 1 NEW_LINE DEDENT ans = ( find_sequence ( n - 1 ) [ 0 ] + 1 , n - 1 ) NEW_LINE if n % 2 == 0 : NEW_LINE INDENT div_by_2 = find_sequence ( n // 2 ) NEW_LINE if div_by_2 [ 0 ] < ans [ 0 ] : NEW_LINE INDENT ans = ( div_by_2 [ 0 ] + 1 , n // 2 ) NEW_LINE DEDENT DEDENT if n % 3 == 0 : NEW_LINE INDENT div_by_3 = find_sequence ( n // 3 ) NEW_LINE if div_by_3 [ 0 ] < ans [ 0 ] : NEW_LINE INDENT ans = ( div_by_3 [ 0 ] + 1 , n // 3 ) NEW_LINE DEDENT DEDENT return ans NEW_LINE DEDENT def find_solution ( n ) : NEW_LINE INDENT a , b = find_sequence ( n ) NEW_LINE print ( a ) NEW_LINE sequence = [ ] NEW_LINE sequence . append ( n ) NEW_LINE while b != - 1 : NEW_LINE INDENT sequence . append ( b ) NEW_LINE _ , b = find_sequence ( b ) NEW_LINE DEDENT return sequence [ : : - 1 ] NEW_LINE DEDENT n = 5 NEW_LINE print ( * find_solution ( n ) ) NEW_LINE