\ 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]