Minimize operations required to obtain N | Function to find the minimum number of operations ; Storing the minimum operations to obtain all numbers up to N ; Initilal state ; Iterate for the remaining numbers ; If the number can be obtained by multiplication by 2 ; If the number can be obtained by multiplication by 3 ; Obtaining the number by adding 1 ; Return the minm operations to obtain n ; Driver Code
#include <bits/stdc++.h> NEW_LINE using namespace std ; int minOperations ( int n ) { int dp [ n + 1 ] ; dp [ 1 ] = 0 ; for ( int i = 2 ; i <= n ; i ++ ) { dp [ i ] = INT_MAX ; if ( i % 2 == 0 ) { int x = dp [ i / 2 ] ; if ( x + 1 < dp [ i ] ) { dp [ i ] = x + 1 ; } } if ( i % 3 == 0 ) { int x = dp [ i / 3 ] ; if ( x + 1 < dp [ i ] ) { dp [ i ] = x + 1 ; } } int x = dp [ i - 1 ] ; if ( x + 1 < dp [ i ] ) { dp [ i ] = x + 1 ; } } return dp [ n ] ; } int main ( ) { int n = 15 ; cout << minOperations ( n ) ; return 0 ; }