Minimum Steps to obtain N from 1 by the given operations | Java 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
import java . util . * ; import java . util . Collections ; import java . util . Vector ; Vector < Integer > v = new Vector < Integer > ( n ) ; class GFG { static Vector < Integer > find_sequence ( int n ) { Vector < Integer > temp = new Vector < Integer > ( ) ; temp . add ( 1 ) ; temp . add ( - 1 ) ; if ( n == 1 ) return temp ; Vector < Integer > arr = find_sequence ( n - 1 ) ; Vector < Integer > ans = new Vector < Integer > ( n ) ; ans . add ( arr . get ( 0 ) + 1 ) ; ans . add ( n - 1 ) ; if ( n % 2 == 0 ) { Vector < Integer > div_by_2 = find_sequence ( n / 2 ) ; if ( div_by_2 . get ( 0 ) < ans . get ( 0 ) ) { ans . clear ( ) ; ans . add ( div_by_2 . get ( 0 ) + 1 ) ; ans . add ( n / 2 ) ; } } if ( n % 3 == 0 ) { Vector < Integer > div_by_3 = find_sequence ( n / 3 ) ; if ( div_by_3 . get ( 0 ) < ans . get ( 0 ) ) { ans . clear ( ) ; ans . add ( div_by_3 . get ( 0 ) + 1 ) ; ans . add ( n / 3 ) ; } } return ans ; } static Vector < Integer > find_solution ( int n ) { Vector < Integer > a = find_sequence ( n ) ; System . out . println ( a . get ( 0 ) ) ; Vector < Integer > sequence = new Vector < Integer > ( ) ; sequence . add ( n ) ; while ( a . get ( 1 ) != - 1 ) { sequence . add ( a . get ( 1 ) ) ; Vector < Integer > arr = find_sequence ( a . get ( 1 ) ) ; a . set ( 1 , arr . get ( 1 ) ) ; } Collections . reverse ( sequence ) ; return sequence ; } public static void main ( String args [ ] ) { int n = 5 ; Vector < Integer > res = find_solution ( n ) ; for ( int i = 0 ; i < res . size ( ) ; i ++ ) { System . out . print ( res . get ( i ) + " ▁ " ) ; } } }