Minimum Steps to obtain N from 1 by the given operations | C # 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 ; Driver Code ; Given N ; Function call
using System ; using System . Collections . Generic ; class GFG { static List < int > find_sequence ( int n ) { List < int > temp = new List < int > ( ) ; temp . Add ( 1 ) ; temp . Add ( - 1 ) ; if ( n == 1 ) return temp ; List < int > arr = find_sequence ( n - 1 ) ; List < int > ans = new List < int > ( n ) ; ans . Add ( arr [ 0 ] + 1 ) ; ans . Add ( n - 1 ) ; if ( n % 2 == 0 ) { List < int > div_by_2 = find_sequence ( n / 2 ) ; if ( div_by_2 [ 0 ] < ans [ 0 ] ) { ans . Clear ( ) ; ans . Add ( div_by_2 [ 0 ] + 1 ) ; ans . Add ( n / 2 ) ; } } if ( n % 3 == 0 ) { List < int > div_by_3 = find_sequence ( n / 3 ) ; if ( div_by_3 [ 0 ] < ans [ 0 ] ) { ans . Clear ( ) ; ans . Add ( div_by_3 [ 0 ] + 1 ) ; ans . Add ( n / 3 ) ; } } return ans ; } static List < int > find_solution ( int n ) { List < int > a = find_sequence ( n ) ; Console . WriteLine ( a [ 0 ] ) ; List < int > sequence = new List < int > ( ) ; sequence . Add ( n ) ; while ( a [ 1 ] != - 1 ) { sequence . Add ( a [ 1 ] ) ; List < int > arr = find_sequence ( a [ 1 ] ) ; a . Insert ( 1 , arr [ 1 ] ) ; } sequence . Reverse ( ) ; return sequence ; } public static void Main ( String [ ] args ) { int n = 5 ; List < int > res = find_solution ( n ) ; for ( int i = 0 ; i < res . Count ; i ++ ) { Console . Write ( res [ i ] + " ▁ " ) ; } } }