Another Cow Number Game

Interview

Time limit1sMemory limit128 MB

Summary

Starting from N, repeatedly apply the Collatz rule (3N+1 if odd, N/2 if even) and count the steps until N reaches 1.

Level: Easy3 of 10
Topics: Simulation, Math, Implementation
Solved: No attempts yet

Problem

The cows are playing a silly number game again. Bessie is tired of losing and wants you to help her cheat.

In this game, a cow supplies an integer $N$ ( $1 \le N \le 1{,}000{,}000$ ). This is move 0. Then the following rules are repeated:

If $N$ is odd, multiply $N$ by 3 and add 1 ( $N \leftarrow 3N + 1$ ).
If $N$ is even, divide $N$ by 2 ( $N \leftarrow N / 2$ ).

Each time the number is multiplied or divided, the score increases by one point. The game ends -- and the score is finalized -- when $N$ becomes 1. If $N$ is initially 1, the score is 0.

Here is an example with $N$ starting at 5:

        N     Next Value    Comment    Score
        5        16          3*5+1       1
       16         8           16/2       2
        8         4            8/2       3
        4         2            4/2       4
        2         1            2/2       5

The final score is 5.

Input

Line 1: A single integer $N$

Output

Line 1: A single integer, the score for this game when starting at $N$

Examples3

Example 1
Input
```
112
```
Expected output
```
20
```
Example 2
Input
```
5
```
Expected output
```
5
```
Example 3
Input
```
1
```
Expected output
```
0
```