Question
We are captured by robot army on their space station. Our space ship pilot is in the prison which is in level 1. There is only one way how to escape and it's rescuing your space ship pilot. It mean's moving from level N to level 1. However because it's very risky you need to get to the prison in the least number of steps as possible.
Conditions
There are 4 ways how to move:
- Move from level N to level N - 1
e.g. from 12 to 11
- Move from level N to level N + 1
e.g. from 12 to 13
- Use teleport from level 2k to level k
e.g. from 12 to 6
- Use teleport from level 3k to level k
e.g. from 12 to 4
- Move from level N to level N - 1
Teleports are only one-way (you can get from 12 to 4 but it's imposible to get from 4 to 12)
- Every action takes one step
Input
Input should be read from STDIN, or the closest alternative in your programming language. Input consists of an integer n
where 1 <= n <= 10^8
.
Output
The output should be the minimum number of steps it takes to go from n
to level 1.
Examples
Level Minimum number of steps
1 0
8 3
10 3
267 7
100,000,000 25
Try to code program that will help us to save our space ship pilot from the prison in the shortest time and return home!
The shortest code will win!