Minimum repeated addition of even divisors of N required to convert N to M | C ++ 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
#include <bits/stdc++.h> NEW_LINE using namespace std ; const int INF = 1e7 ; const int max_size = 100007 ; int dp [ max_size ] ; 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 = min ( op , 1 + min_op ( cur + i , M ) ) ; } if ( ( cur / i ) != i && ( cur / i ) % 2 == 0 ) { op = min ( op , 1 + min_op ( cur + ( cur / i ) , M ) ) ; } } } return dp [ cur ] = op ; } int min_operations ( int N , int M ) { for ( int i = N ; i <= M ; i ++ ) { dp [ i ] = -1 ; } return min_op ( N , M ) ; } int main ( ) { int N = 6 , M = 24 ; int op = min_operations ( N , M ) ; if ( op >= INF ) cout << " - 1" ; else cout << op << " STRNEWLINE " ; return 0 ; }