TopCoder Statistics - Problem Statement

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
1

4844

Returns: -1
10

18929

Returns: -1
9

712211

Returns: -1
4

10

Returns: -1
4

83198

Returns: -1
92

897

Returns: -1
9

911

Returns: -1
888

119731

Returns: -1
38

99

Returns: -1
46

656

Returns: -1
941533

964384

Returns: -1
9

8558

Returns: -1
286

21229

Returns: -1
53

86497

Returns: -1
29969

648178

Returns: -1
65

5201

Returns: -1
10

341381

Returns: -1
4069

8529

Returns: -1
3

35845

Returns: -1
2748

827341

Returns: -1
5548

448938

Returns: -1
577

978660

Returns: -1
8

2075

Returns: -1
2

2859

Returns: -1
2

445885

Returns: -1
3083

7521

Returns: -1
53

7346

Returns: -1
58

4265

Returns: -1
17

54

Returns: -1
1234

9529

Returns: -1
7

1791

Returns: -1
650

708

Returns: -1
31533

83

Returns: -1
66521

93

Returns: -1
946312

20825

Returns: -1
9590

714920

Returns: -1
71746

664

Returns: -1
2715

36

Returns: -1
187

149707

Returns: -1
710

198

Returns: -1
71

4016

Returns: -1
31286

781

Returns: -1
6735

29

Returns: -1
63

90

Returns: -1
240632

8595

Returns: -1
24242

1

Returns: -1
44283

757512

Returns: -1
280

565707

Returns: -1
31853

3047

Returns: -1
198085

7

Returns: -1
6

722443

Returns: 12
985

851518

Returns: 8
20675

372163

Returns: 3
99779

399119

Returns: 2
7211

519259

Returns: 5
93

545481

Returns: 9
38734

464818

Returns: 3
275497

826492

Returns: 1
4

444007

Returns: 13
276826

553653

Returns: 1
1

728272

Returns: 13
725

626950

Returns: 8
1919

621921

Returns: 6
36

378879

Returns: 11
5

513691

Returns: 13
333543

333543

Returns: 0
61223

734686

Returns: 3
68020

612184

Returns: 2
2

342783

Returns: 14
270105

810316

Returns: 1
1

5

Returns: -1
4

22

Returns: -1
1

2

Returns: -1

Statistics

Problem Statement for "MultiplyXPlusOne"

Problem Statement

Definition

Constraints

Examples