Minimum repeated addition of even divisors of N required to convert N to M | Java program for the above approach ; INF is the maximum value which indicates Impossible state ; Stores the dp states ; Recursive Function that considers all possible even divisors of cur ; Indicates impossible state ; Check dp [ cur ] is already calculated or not ; Initially it is set to INF that meanswe cur can 't be transform to M ; Loop to find even divisors of cur ; If i is divisor of cur ; If i is even ; Find recursively for cur + i ; Check another divisor ; Find recursively for cur + ( cur / i ) ; Finally store the current state result and return the answer ; Function that counts the minimum operation to reduce N to M ; Initialise dp state ; Function call ; Driver Code ; Given N and M ; Function call ; INF indicates impossible state
import java . util . * ; class GFG { static int INF = ( int ) 1e7 ; static int max_size = 100007 ; static int [ ] dp = new int [ max_size ] ; static int min_op ( int cur , int M ) { if ( cur > M ) return INF ; if ( cur == M ) return 0 ; if ( dp [ cur ] != - 1 ) return dp [ cur ] ; int op = INF ; for ( int i = 2 ; i * i <= cur ; i ++ ) { if ( cur % i == 0 ) { if ( i % 2 == 0 ) { op = Math . min ( op , 1 + min_op ( cur + i , M ) ) ; } if ( ( cur / i ) != i && ( cur / i ) % 2 == 0 ) { op = Math . min ( op , 1 + min_op ( cur + ( cur / i ) , M ) ) ; } } } return dp [ cur ] = op ; } static int min_operations ( int N , int M ) { for ( int i = N ; i <= M ; i ++ ) { dp [ i ] = - 1 ; } return min_op ( N , M ) ; } public static void main ( String [ ] args ) { int N = 6 , M = 24 ; int op = min_operations ( N , M ) ; if ( op >= INF ) System . out . print ( " - 1" ) ; else System . out . print ( op + "NEW_LINE"); } }