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
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
sharif ullah: 2016-01-26 10:05:58

DP!!!!!!!!!;
when n==6;
n%2==0;
n%3==0;
when n==18;
n%2==0;
n%3==0;
........................................

Last edit: 2016-01-26 10:10:30
Arpan Mukherjee: 2015-09-26 23:13:07

Using dp,still getting Runtime Error Any help?

EDIT: Declare the array globally,cost me 1 WA

Last edit: 2015-09-26 23:39:51
boovi: 2015-08-29 16:33:48

My First DP!!:)

sameer Hussain: 2015-07-15 18:35:00

Easy DP :)

Last edit: 2015-07-15 19:02:00

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