## MST1 - Minimum Step To One

no tags

Problem Statement:

Problem statement is very easy . On a positive integer, you can perform any one of the following 3 steps.

1.)  Subtract 1 from it. ( n = n - 1 )

2.)  If its divisible by 2, divide by 2. ( if n % 2 == 0 , then n = n / 2  )

3.)  If its divisible by 3, divide by 3. ( if n % 3 == 0 , then n = n / 3  )

Given a positive integer  n and you task is find the minimum number of steps that takes n to one .

Input:

The input contains an integer T (1 ≤  T ≤  100) number of test cases. Second line input is N (0 < N ≤ 2*107 ) that indicates the positive number.

Output:

For each case, print the case number and minimum steps.

Sample Input/Output:

 Sample Input Sample Output 3  1  4  7 Case 1: 0  Case 2: 2  Case 3: 3

For example :-

1.) For N= 1 , output: 0

2.) For N = 4 , output: 2  ( 4  /2 = 2  /2 = 1 )

3.) For N = 7 , output: 3  (  7 -1 = 6  /3 = 2   /2 = 1 )

hide comments
 < Previous 1 2 3 4 Next > solvertobe: 2020-10-07 15:21:29 Ac in on go. My third DP. deerawat: 2020-05-24 22:04:03 AC IN ONE GO raghav6: 2018-12-31 14:31:57 Use Vector instead of the Array it is more time and space efficient. ram_24: 2018-06-25 06:10:08 output format cost me 1 WA :( adityavr9: 2018-06-23 06:48:02 Please note the Output Format. It is: Case : Shikhor Roy: 2018-05-28 18:55:51 Recursive DP in java causes NZEC ERROR (may be stack overflow occur)...but iterative DP is fine !!! Last edit: 2018-05-28 18:56:35 asif_mohammad: 2018-02-14 10:57:40 ACC in one go. BFS nilesh101: 2018-01-30 02:34:23 can it not be done by simply using a while loop? by applying some conditions? bholebaba: 2018-01-29 21:59:58 All these time I was printing just the required values and not the case nos :(, cbdavide: 2017-07-28 23:16:31 First DP solution, I feel really, really happy :) After two TLE submissions using a map as a table, until I changed it to an array. Last edit: 2017-07-28 23:17:44

 Added by: Shipu Ahamed Date: 2013-05-11 Time limit: 1s Source limit: 50000B Memory limit: 1536MB Cluster: Cube (Intel G860) Languages: All except: ASM64