A tabulation based solution
#include <bits/stdc++.h> NEW_LINE using namespace std ; int getMinSteps ( int n ) { int table [ n + 1 ] ; table [ 1 ] = 0 ; for ( int i = 2 ; i <= n ; i ++ ) { if ( ! ( i % 2 ) && ( i % 3 ) ) table [ i ] = 1 + min ( table [ i - 1 ] , table [ i / 2 ] ) ; else if ( ! ( i % 3 ) && ( i % 2 ) ) table [ i ] = 1 + min ( table [ i - 1 ] , table [ i / 3 ] ) ; else if ( ! ( i % 2 ) && ! ( i % 3 ) ) table [ i ] = 1 + min ( table [ i - 1 ] , min ( table [ i / 2 ] , table [ i / 3 ] ) ) ; else table [ i ] = 1 + table [ i - 1 ] ; } return table [ n ] ; }