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
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
ayush_1996: 2017-07-15 09:49:52

My First DP :D

Omar: 2017-06-14 07:02:14

I solved it recursive + memo (top-down) in 0.48 sec. , and this is my code
http://ideone.com/9wiwfE

ekjot_kaur281: 2017-06-12 20:22:49

Got 3 WA because i didnt give space after colon

Nafis Islam: 2017-05-17 16:21:06

Top down dp works :D

cyanide_mind: 2017-04-08 20:03:21

My First DP :)


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