\ Untitled - /g/pasta 2.4
From kira, 5 Years ago, written in Plain Text.
Embed
1. Problem Statement:
2. On a positive integer, you can perform any one of the following 3 steps.
3. 1.) Subtract 1 from it. ( n = n - 1 )  ,
4. 2.) If its divisible by 2, divide by 2. ( if n % 2 == 0 , then n = n / 2  )  ,
5. 3.) If its divisible by 3, divide by 3. ( if n % 3 == 0 , then n = n / 3  ).
6. Now the question is, given a positive integer n, find the minimum number of steps that takes n to 1
7.
8.
9. [code]
10.
11. int memo[n+1]; // we will initialize the elements to -1 ( -1 means, not solved it yet )
12.
13. int getMinSteps ( int n )
14.
15. {
16.
17. if ( n == 1 )  return 0;  // base case
18.
19. if( memo[n] != -1 ) return memo[n];  // we have solved it already :)
20.
21. int r = 1 + getMinSteps( n - 1 );  // '-1' step .  'r' will contain the optimal answer finally
22.
23. if( n%2 == 0 )   r  =  min( r , 1 + getMinSteps( n / 2 ) ) ;  //  '/2' step
24.
25. if( n%3 == 0 )   r  =  min( r , 1 + getMinSteps( n / 3 ) ) ;  //  '/3' step
26.
27. memo[n] = r ;  // save the result.
28.
29. return r;
30.
31. }
32.
33. [/code]