TopCoder Statistics - Problem Statement

Problem Statement

You have two positive integers: the first one is a, the second one is b.

You also have a red button and a blue button.
Whenever you push the red button, both your numbers are incremented by 1.
Whenever you push the blue button, both your numbers are multiplied by 2.

Your goal is to change the pair (a, b) into the pair (newA, newB).

You are given the ints a, b, newA, and newB.
If there is a sequence of zero or more button pushes that accomplishes your goal, return the length of the shortest such sequence. Otherwise, return -1.

Definition

Class:: DoubleOrOneEasy
Method:: minimalSteps
Parameters:: int, int, int, int
Returns:: int
Method signature:: int minimalSteps(int a, int b, int newA, int newB)
(be sure your method is public)

Notes

The operations can produce arbitrarily large integers. For example, if you just push the blue button 1000 times in a row, you will get the numbers a*2^1000 and b*2^1000.

Constraints

a will be between 1 and 1,000,000,000, inclusive.
b will be between 1 and 1,000,000,000, inclusive.
newA will be between 1 and 1,000,000,000, inclusive.
newB will be between 1 and 1,000,000,000, inclusive.

Examples

100

1000

101

1001

Returns: 1

Just push the red button once.
100

1000

202

2002

Returns: 2

The best solution is to push the red button followed by the blue button. This performs the operation +1 followed by the operation *2. Another valid solution is to push the blue button once and then the red button twice to perform the operations *2, +1, and +1. This solution is not optimal because the previous solution contains fewer operations.
2

2

1

1

Returns: -1

We are unable to decrease a and b.
1

111111111

8

888888888

Returns: 3
1

111111111

9

999999999

Returns: -1
1

2

999999999

1000000000

Returns: 999999998
5

8

5

8

Returns: 0
100

200

499

899

Returns: 28
100

200

210

410

Returns: 6
100

100

800

800

Returns: 3
100

100

899

899

Returns: 17
100

100

199

199

Returns: 99
100

100

999999999

999999999

Returns: 57
100

100

999999999

1000000000

Returns: -1
100

200

400

800

Returns: 2
100

200

399

799

Returns: -1
76362

724813095

77200

724813933

Returns: 838
53

7598541

7227

972613691

Returns: 15
12178343

55631481

194853525

890103733

Returns: 8
2044

43922

33543752

719672904

Returns: 22
318066

837890634

318068

837890636

Returns: 2
77

3778

20324374

990519318

Returns: 23
390

424

920853974

992157142

Returns: 81
631

82402864

5445

659223309

Returns: 54
8308

2901472

2128063

742778047

Returns: 19
261

9

533

29

Returns: 7
4535875

154

580592002

19714

Returns: 8
59

2696395

1888

86284640

Returns: 5
45

669

67903539

722214963

Returns: 46
340

9300840

22098

595254098

Returns: 13
9

7949410

630

508762294

Returns: 10
104

37539

223

75093

Returns: 9
249

6

609

123

Returns: 57
2

89

19398989

749207885

Returns: 30
69

275

573

2221

Returns: 7
9

3434730

41

13738925

Returns: 4
745

18

753

26

Returns: 8
426820

825108

437069764

844916676

Returns: 20
46591

9933

745465

158937

Returns: 6
72743297

6037257

581947017

48298697

Returns: 84
6844

478594686

13691

957189375

Returns: 3
825

25900842

26489

828827033

Returns: 10
275

6361316

35534

814248782

Returns: 13
8211904

9025731

525565288

577650216

Returns: 61
136668

23

559799763

101843

Returns: 21
82910816

921720308

82910821

921720313

Returns: 5
4841

4841

19390

19390

Returns: 9
17740690

17740690

17740697

17740697

Returns: 7
7319

7319

959485370

959485370

Returns: 27
589

589

618144259

618144259

Returns: 25
30224

30224

990583493

990583493

Returns: 28
398664

398664

816466078

816466078

Returns: 17
7

7

975196408

975196408

Returns: 36
63705949

63705949

63706472

63706472

Returns: 523
43

43

704

704

Returns: 5
62267781

62267781

996286044

996286044

Returns: 102
524803

524803

537404834

537404834

Returns: 20
31

31

3970

3970

Returns: 8
25058287

25058287

801865369

801865369

Returns: 13
472056

472056

1888240

1888240

Returns: 6
429846

429846

880324875

880324875

Returns: 15
88

88

177

177

Returns: 2
64094468

64094468

512755849

512755849

Returns: 17
7236901

7236901

926323549

926323549

Returns: 13
5

5

638297468

638297468

Returns: 43
17382

17382

569581838

569581838

Returns: 20
35

72655

90598

82

Returns: -1
457

143709

79256326

7899

Returns: -1
739

9271241

79

29410

Returns: -1
416

68

8

2820454

Returns: -1
460495063

1924635

4316

40573

Returns: -1
306331

23145

3

10296

Returns: -1
465

4875933

55265769

317398

Returns: -1
946969

966

6067

624

Returns: -1
16688

115166209

4521314

9106115

Returns: -1
83539434

82

3876

620

Returns: -1
9251

407890888

3378

9772508

Returns: -1
933628020

61917107

61578242

9

Returns: -1
3944

6679

5240761

71867

Returns: -1
33

5294733

180114971

7639

Returns: -1
92671857

246352131

524772

6

Returns: -1
8

92148

91345258

5

Returns: -1
6868003

838779

34897816

41

Returns: -1
560815924

3070

1896282

403446

Returns: -1
10

98

45

5641

Returns: -1
7432

75

2

498

Returns: -1
9

55

72

164

Returns: 28
1

3

4

6

Returns: 3
1

2

999999997

999999999

Returns: 499999999
1

1

4

4

Returns: 2
1

1

11

11

Returns: 5
1

2

100002

100003

Returns: 100001
2

2

50

10

Returns: -1
1

1

1000000000

1000000000

Returns: 41
2

1

493

485

Returns: 64
1

2

990000000

991048576

Returns: 969
2

4

100

102

Returns: 98
1

27

19

123

Returns: 7
1

1

2

2

Returns: 1
10

20

29

49

Returns: 6
2

5

1167230

1167422

Returns: 18246
1

1

10

10

Returns: 4
1

2

23

27

Returns: 8
1

1

1000000000

999999999

Returns: -1
3

4

23

27

Returns: 6
3

3

4

5

Returns: -1
4

4

7

7

Returns: 3
1

1

255

255

Returns: 14
1

1

31

31

Returns: 8
3

5

12

14

Returns: 9
1

2

800004398

800004406

Returns: 100000553
1000

2

2000

1002

Returns: 1000
1

1

8

8

Returns: 3
1

1001

1000

2000

Returns: 999
1

500000000

500000000

999999999

Returns: 499999999
10

26

14111245

14111757

Returns: 440974
1

2

3

7

Returns: -1
1

5

12

16

Returns: 11
7

2

14

9

Returns: 7
2

2

2026

2026

Returns: 16
100

10000

105

10005

Returns: 5
1

3

2

4

Returns: 1
2

2

14

14

Returns: 4
2

4

102

104

Returns: 100
5

5

40

40

Returns: 3
2

2

7

7

Returns: 3
1

1

242

242

Returns: 11
1

1

1000000

1000000

Returns: 25
5

5

13

13

Returns: 3
1

1

9

9

Returns: 4
3

5

66384

66896

Returns: 266
1

2

31

32

Returns: 30
9

9

16

16

Returns: 7
2

3

4

5

Returns: 2
6

4

6

2

Returns: -1
2

2

5

5

Returns: 2
4

4

16

16

Returns: 2
1

3

5

7

Returns: 4
7

17

31

51

Returns: 10
9

5

18

14

Returns: 9
1

2

1

3

Returns: -1
65536

65536

805306368

805306368

Returns: 32781
1

1

536870911

536870911

Returns: 56
3

5

8

10

Returns: 5
2

1

1000000000

999999998

Returns: 499999999
2

2

3

6

Returns: -1
2

4

5

7

Returns: 3
5

5

12

12

Returns: 2
6

8

16

20

Returns: 3
1

1

32

32

Returns: 5
3

3

17

17

Returns: 4
3

3

4

4

Returns: 1
2

2

20

20

Returns: 4
3

1

1000000000

999999998

Returns: 999999997
1

1

15

15

Returns: 6
1

1

5

4

Returns: -1
100

100

200

200

Returns: 1
2

4

32

36

Returns: 15
1

1

7

7

Returns: 4
100

100

1

1

Returns: -1
1

2

4

7

Returns: -1
1

100

132768

3376800

Returns: 22
1

1

2

4

Returns: -1
4

8

12

16

Returns: 8
4

6

42

58

Returns: 5
5

5

10

10

Returns: 1
1

10

6

15

Returns: 5
1

2

999999998

1000000000

Returns: 499999999
1

10

4

13

Returns: 3
1

3

12

16

Returns: 6
500000001

499999999

1000000000

1000000000

Returns: -1
1

2

3

4

Returns: 2
982

982

5257

5257

Returns: 335
1

1

64

64

Returns: 6
3

3

1

1

Returns: -1
100

100

50

50

Returns: -1
1

1

1

1

Returns: 0
2

11

1

10

Returns: -1
1

1

364364

364364

Returns: 27
2

2

2

4

Returns: -1
1

101

1000

1801

Returns: -1
1

2

100000

100001

Returns: 99999
1

2

10000000

1000000000

Returns: -1
6

6

17

17

Returns: 4
3

3

9

9

Returns: 3
1

3

2

5

Returns: -1
4

4

6

6

Returns: 2
101

122

333

375

Returns: 67
1

1

101

101

Returns: 9
3

3

1000000

1000000

Returns: 23
1

1

1000000000

100

Returns: -1
500000000

500000000

999999999

999999999

Returns: 499999999
1

536870913

8

8

Returns: -1
2

2

100

100

Returns: 7
1

2

42

74

Returns: 7
3

5

20

22

Returns: 17
2

1

3

1

Returns: -1

Statistics

Problem Statement for "DoubleOrOneEasy"

Problem Statement

Definition

Notes

Constraints

Examples