#include <iostream>
#include <string.h>
#include <stdio.h>
using namespace std ;
#define min(a,b) ( (a) < (b) ? (a) : (b))
int memo[10+1] ;
void reset_memo(){
cout <<endl ;
cout << "RESETTING MEMO" <<endl ;
for(int i = 0 ; i < 11 ; i++){
memo[i] = -1 ;
}
}
int getMinSteps ( int n ){
cout << "=============================="<<endl ;
cout << "entering the function" <<endl ;
if ( n == 1 ){ cout << "n = 1" <<endl ; return 0;} // base case
if( memo[n] != -1 ){
cout << "critical : found -1" <<endl;
return memo[n];} // we have solved it already :)
int r = 1 + getMinSteps( n - 1 ); // '-1' step . 'r' will contain the optimal answer finally
if( n%2 == 0 ){ cout << "n is div by 2" <<endl ; r = min( r , 1 + getMinSteps( n / 2 ) ) ;} // '/2' step
if( n%3 == 0 ){cout << "n is div by 3 " <<endl ; r = min( r , 1 + getMinSteps( n / 3 ) ) ;} // '/3' step
cout << "r added is " << r <<endl ;
memo[n] = r ; // save the result. If you forget this step, then its same as plain recursion.
return r;
}
int main(){
int n ;
int res = 0 ;
reset_memo() ;
while(true){
cout << endl <<endl ;
cout << "enter next number" <<endl ;
cin >> n ;
if( n == -1 ) {cout << "THE END " <<endl ; break ;}
else{ res = getMinSteps(n) ;
cout << "result : " <<res <<endl ;
reset_memo() ;
}
}
}
