MultiplyXPlusOne | Topcoder Archive

Problem Statement

There is a card and at the beginning there is a number s on it, in each step you can do one of this operation:

Suppose the number on this card is x, change it into 2x+1.
Suppose the number on this card is x, change it into 3x+1.

Please compute and return the minimal number of operations to change the number of your card into t. If that is impossible, return -1.

Definition

Class:: MultiplyXPlusOne
Method:: minimalSteps
Parameters:: int, int
Returns:: int
Method signature:: int minimalSteps(int s, int t)
(be sure your method is public)

Constraints

s will be between 0 and 1,000,000, inclusive.
t will be between 0 and 1,000,000, inclusive.

Examples

```
1
```
```
22
```
```
Returns: 3
```
First we use operation 1, the number will become 2*1+1 = 3. Then we use operation 1 again, we get 3*2+1 = 7. Last we use operation 2, it will be 7*3+1 = 22.
```
1
```
```
31
```
```
Returns: 3
```
Although we can get it by 1, 3, 7, 15, 31, we could use less steps by 1, 3, 10, 31.
```
100
```
```
99
```
```
Returns: -1
```
We can't decrease the number, so it is impossible to get 99 from 100.
```
55555
```
```
1000000
```
```
Returns: 3
```
```
1
```
```
1
```
```
Returns: 0
```

This problem statement is the exclusive and proprietary property of Topcoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of Topcoder, Inc. is strictly prohibited. (c)2024, Topcoder, Inc. All rights reserved.