MST1  Minimum Step To One
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*10^{7} ) 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
raghav6:
20181231 14:31:57
Use Vector instead of the Array it is more time and space efficient. 

ram_24:
20180625 06:10:08
output format cost me 1 WA :( 

adityavr9:
20180623 06:48:02
Please note the Output Format. It is:


Shikhor Roy:
20180528 18:55:51
Recursive DP in java causes NZEC ERROR (may be stack overflow occur)...but iterative DP is fine !!! Last edit: 20180528 18:56:35 

asif_mohammad:
20180214 10:57:40
ACC in one go. BFS


nilesh101:
20180130 02:34:23
can it not be done by simply using a while loop? by applying some conditions?


bholebaba:
20180129 21:59:58
All these time I was printing just the required values and not the case nos :(, 

cbdavide:
20170728 23:16:31
First DP solution, I feel really, really happy :)


ayush_1996:
20170715 09:49:52
My First DP :D


Omar:
20170614 07:02:14
I solved it recursive + memo (topdown) in 0.48 sec. , and this is my code

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