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
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 :)

samarjeet27: 2016-04-15 12:04:16

Why does Global DP Array gives AC while Local Array gives WA ?

darkhire21: 2016-04-10 08:22:57

TOP down TLE ...!!

gohanssj9: 2016-02-24 15:33:12

first dp :D

sharif ullah: 2016-01-26 10:06:00

Last edit: 2016-01-26 10:06:34

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