MST1 - Minimum Step To One
Problem statement is very easy. On a positive integer, you can perform any one of the following 3 steps.
- Subtract 1 from it. (n = n - 1)
- If it is divisible by 2, divide by 2. (if n % 2 == 0, then n = n / 2)
- If it is 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 the minimum number of steps.
Example
Input: 3 1 4 7 Output: Case 1: 0 Case 2: 2 Case 3: 3
Explanation
- For N = 1, output: 0
- For N = 4, output: 2 (4 /2 = 2 /2 = 1)
- For N = 7, output: 3 ( 7 -1 = 6 /3 = 2 /2 = 1)
hide comments
Arpan Mukherjee:
2015-09-26 23:13:07
Using dp,still getting Runtime Error Any help?
|
|
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 |
|
surbhit21:
2015-03-04 07:56:11
first DP !! :)
|
|
nrl 7:
2014-12-22 11:10:49
Only 2 correct submissions in Java, due to a very odd-style of input specified. :\ |
|
Rohit Meena:
2014-10-22 13:33:04
why i got wrong ans <snip> Last edit: 2023-03-16 12:14:11 |
|
^_^:
2014-10-16 12:20:33
My first dp :) |
|
karan:
2014-10-03 10:00:12
first dp :) |
|
Girish Rathi:
2014-09-07 03:10:39
easy one
|
|
vikrant:
2014-08-05 19:51:08
use dp rather than recursive
|
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 |