Problem Statement
- Add a to your current number.
- Multiply your current number by b.
You are given the
Definition
- Class:
- MultiplyAddPuzzle
- Method:
- minimalSteps
- Parameters:
- long, long, long, long
- Returns:
- long
- Method signature:
- long minimalSteps(long s, long t, long a, long b)
- (be sure your method is public)
Constraints
- s will be between 0 and 1,000,000,000,000,000,000 (10^18), inclusive.
- t will be between 0 and 1,000,000,000,000,000,000 (10^18), inclusive.
- a will be between 0 and 1,000,000,000,000,000,000 (10^18), inclusive.
- b will be between 0 and 1,000,000,000,000,000,000 (10^18), inclusive.
Examples
10
40
4
2
Returns: 2
At the beginning you have the number 10. In each step you can either add 4 to your number, or you can multiply it by 2. You want to reach the number 40. The optimal solution is to use multiplication twice, changing 10 to 10*2 = 20 and then changing 20 to 20*2 = 40.
10
28
4
2
Returns: 2
The same setting, but now the goal is the number t = 28. Again, it is possible to reach this number in two steps. In the first step we add 4, going from 10 to 10+4 = 14. In the second step we multiply by 2, going from 14 to 14*2 = 28.
10
99
4
2
Returns: -1
Whatever you do, the number you'll have will always be even, so it's impossible to reach the odd number 99.
345
12345
1
10
Returns: 895
1
1000000000000000000
1
0
Returns: 999999999999999999
1
1000000000000000000
3
1
Returns: 333333333333333333
1
1024
0
2
Returns: 10
1
1023
0
2
Returns: -1
45654654
45654654
0
0
Returns: 0
5463546
0
0
0
Returns: 1
1
1000000000000000000
52579
2
Returns: 19018999980981
1
2
2
0
Returns: 2
3
2
2
0
Returns: 2
3
0
0
0
Returns: 1
0
0
0
0
Returns: 0
1
3
2
1
Returns: 1
4
332
8
1
Returns: 41
2
263243407684534272
0
6
Returns: 22
0
44594133991056
2
5574266748882
Returns: 5
5788666556073
0
0
0
Returns: 1
0
0
7
0
Returns: 0
604499041098525
604499041098525
58512495745255
46993491
Returns: 0
1
9268
2
2
Returns: 17
7
73069039522
2435634647
2
Returns: 8
155
0
2
0
Returns: 1
1
22
1
2
Returns: 6
7
4399194
10
2
Returns: 24
9584508598251544
776345196458375064
0
9
Returns: 2
0
5
5
2
Returns: 1
5373507075
923294432702319713
923281530911832638
7
Returns: 5
1
121310582179855719
681520124605931
1
Returns: 178
31613357
31613357
0
435845062
Returns: 0
1
51
10
1
Returns: 5
0
24
1
1
Returns: 24
2
19562256
10
2
Returns: 33
0
8
2
62
Returns: 4
2
12394324296208
8
2489410
Returns: 3
4
231281530775241896
4
19273460897936824
Returns: 5
24568952501179854
18
9
0
Returns: 3
1
2984087853009
8
331565317001
Returns: 2
0
103308522881313132
1
103308522881313132
Returns: 2
1
20955468
2
6985156
Returns: 2
6
717042327086145941
1
2524
Returns: 10
5
146739128283665
79019455185
2
Returns: 15
2
858314527835264754
2
5
Returns: 49
1
21
2
1
Returns: 10
1
5
5
0
Returns: 2
386341297793
386341297817
1
1
Returns: 24
1
0
0
0
Returns: 1
4
5
1
1
Returns: 1
0
4
2
0
Returns: 2
0
0
2
0
Returns: 0
823853445
823853445
2
9633201405269
Returns: 0
2
6986112871
6986112869
1
Returns: 1
0
874012094122230405
5
9
Returns: 35
2
2
0
1
Returns: 0
49552171598
49552171602
2
77688518383581170
Returns: 2
1
1
2
47656706055956163
Returns: 0
0
0
3
7
Returns: 0
4
260
1
1
Returns: 256
0
834
6
1
Returns: 139
9
855098893301
1
85509889330
Returns: 3
0
640220949025714604
4
7
Returns: 37
2
1369132438630276
4
61108
Returns: 5
1
3
1
0
Returns: 2
1
3
2
2
Returns: 1
2
451270179062136828
1
3
Returns: 58
0
20
10
0
Returns: 2
1
2
2
0
Returns: 2
1
898840013466841625
2
5
Returns: 43
1
6015828751310
1
3007914375655
Returns: 2
9
7409673756708384
7409673756708375
1
Returns: 1
2
0
50047098848741925
0
Returns: 1
3
32
1
2
Returns: 4
2
0
2
0
Returns: 1
6
6
0
1
Returns: 0
2
6669029109209340
6
333451455460467
Returns: 4
0
2
2
0
Returns: 1
1
679079712434541217
0
679079712434541217
Returns: 1
1
1
0
1
Returns: 0
9
66
4
6
Returns: 4
2
518690518069171
833401
622376590
Returns: 3
2
0
1
0
Returns: 1
46416077
0
0
0
Returns: 1
777081679127899132
777081679127899132
1
4
Returns: 0
4
119827163207196896
0
310574
Returns: 3
6063567185
0
1838699353693967
0
Returns: 1
0
12021516436
6010758218
8
Returns: 2
7
596578761226
596578761219
1
Returns: 1
1
1
2
64698182647
Returns: 0
1
2467185290444102
2
822395096814700
Returns: 3
7
506179622488737242
2
33745308165915816
Returns: 6
1524966571
818710194490189272
1
2
Returns: 42
98881932784811
768905909334722390
2
6
Returns: 12
90805003272
523472773667428872
0
7
Returns: 8
2
44765376612198272
2613100299
2
Returns: 33
0
438
6
8
Returns: 5
45039
792349592369856754
5
2
Returns: 62
2
2
2
6
Returns: 0
72203509147125
72203509147227
2
1
Returns: 51
0
0
0
1
Returns: 0
2
576460752303423488
0
2
Returns: 58
0
4
2
7152985
Returns: 2
0
996839739978563995
199367947995712799
0
Returns: 5
0
1512580388
2
756290194
Returns: 2
480419338015308
983898804255363850
1
2
Returns: 21
5763313026
57633130282200
2
10
Returns: 7
0
0
0
77296
Returns: 0
2
227443549395598928
10
8
Returns: 36
2
262144
0
2
Returns: 17
1
549755813888
0
2
Returns: 39
65
774860382080078125
0
5
Returns: 23
0
0
2
1
Returns: 0
1
700461024973592524
1
2
Returns: 88
2
4194304
0
2
Returns: 21
1
65669626824
2
6
Returns: 22
1
250400575150969430
1
5
Returns: 49
1
24063705
891248
9
Returns: 4
2
504352950537600
4
9168360
Returns: 3
8
76638936
2
2
Returns: 34
2
0
7132159
0
Returns: 1
2
23
7
1
Returns: 3
0
0
0
0
Returns: 0
5
0
0
0
Returns: 1
0
709694719834842310
2
2
Returns: 91
1
4504626811
83419015
1
Returns: 54
0
18
9
2
Returns: 2
2
55
1
1
Returns: 53
0
0
1
2
Returns: 0
0
0
0
5
Returns: 0
2
0
0
0
Returns: 1
0
319634557064148060
2
7
Returns: 38
77795109175320
77795109175320
2
1
Returns: 0
1
6668561
6668561
0
Returns: 2
5
176
2
2
Returns: 6
8
669618386848288786
1
2
Returns: 77
2
6
2
1
Returns: 2
636
0
1
0
Returns: 1
2
2
0
1
Returns: 0
0
701347023389896200
350673511694948100
1
Returns: 2
1
1
1
0
Returns: 0
1
2
2
0
Returns: 2
0
17294403
3
7
Returns: 9
8
15
7
1
Returns: 1
1
1
668032758448845031
0
Returns: 0
1
1
2
1
Returns: 0
2
0
1
1
Returns: -1
40
2
2
0
Returns: 2
6
0
1
7
Returns: -1
1
30
0
2
Returns: -1
0
7227448402
2
1
Returns: 3613724201
1
1
2
1
Returns: 0
1
0
1
2
Returns: -1
2
9
2
1
Returns: -1
2
1
0
1
Returns: -1
8
6
2
10
Returns: -1
0
6709
42598819038596
1
Returns: -1
3
2
7
2
Returns: -1
2
1
1
0
Returns: 2
1
3211917
32422
1
Returns: -1
1
619354027259028
1
0
Returns: 619354027259027
2
2
2
1
Returns: 0
637204383177781352
0
2
1
Returns: -1
0
0
2
33459220867690386
Returns: 0
0
0
2
0
Returns: 0
150217265155
1
0
0
Returns: -1
0
1
1
1
Returns: 1
2
2
1
1
Returns: 0
0
0
1
972333
Returns: 0
8
9
1
0
Returns: 1
0
1
1
1
Returns: 1
6
6461100596
9543363
1
Returns: -1
2
84584336161486464
3
2
Returns: -1
1
0
2
0
Returns: 1
7
5
6
8
Returns: -1
2
0
1
2923506558287480
Returns: -1
1
5
90150
0
Returns: -1
2
1
5
0
Returns: -1
174814
2
1
166629597570
Returns: -1
2
2
2
1
Returns: 0
9784688167
0
2
2
Returns: -1
1
36844001936301
0
192
Returns: -1
0
0
3
10
Returns: 0
0
7
69
2
Returns: -1
9
1
5
2
Returns: -1
4
1
2
1
Returns: -1
833114397
2
1
0
Returns: 3
31920
1
1
0
Returns: 2
6
6429131987867022
8
2
Returns: 803641498483377
0
0
0
8
Returns: 0
9615937242668
1
9
0
Returns: -1
1
249947229784
0
2
Returns: -1
5532218331007
7
1
9
Returns: -1
98374999983367425
5360346646
1
4
Returns: -1
40
5
8037116534018704
6
Returns: -1
61
512399422745329551
9
33
Returns: 1725250581634115
98
812440861332123760
27
29
Returns: 1037600078329667
9
636890545796983342
11
57
Returns: 1015774395210552
83
387382397409348123
18
15
Returns: 1434749620034620
13
462658693525565892
80
4
Returns: 1445808417267395
3
522978804100894812
16
20
Returns: 1634308762815299
72
672062551541232603
41
8
Returns: 2048971193723272
11
967711671328198142
28
6
Returns: 5760188519810708
96
518615565344257580
25
5
Returns: 4148924522754061
77
501353328704220546
16
10
Returns: 3133458304401380
65
448865188210196079
9
39
Returns: 1278818200029059
25
708077296795897374
4
26
Returns: 6808435546114407
81
945264896711877954
4
58
Returns: 4074417658240834
20
741629449779133653
83
7
Returns: 1276470653664606
23
588640757523831305
13
41
Returns: 1104391665147915
45
835824775649847932
8
84
Returns: 1243786868526621
3
171253920587364074
4
18
Returns: 2378526674824506
87
165576017468022354
24
6
Returns: 1149833454639044
62
901409491435695332
8
22
Returns: 5121644837702821
83
712513687916539953
38
15
Returns: 1250024013888671
13
311544568954336546
12
10
Returns: 2596204741286145
63
941223512388597938
4
58
Returns: 4056997898226729
80
569215332646903691
51
10
Returns: 1116108495386086
52
710613785871150054
53
7
Returns: 1915401040083965
92
669763529629567482
22
30
Returns: 1014793226711483
24
608965237234467780
13
24
Returns: 1951811657802792
39
946822531396229914
4
22
Returns: 10759346947684424
71
459831542741880476
72
4
Returns: 1596637301187085
10
805474536127030812
8
42
Returns: 2397245643235231
18
979446360709194068
22
39
Returns: 1141545874952472
1000000000000000000
1000000000000000000
1000000000000000000
1000000000000000000
Returns: 0
7
4
2
0
Returns: 3
5
1
1
0
Returns: 2
42
3
3
0
Returns: 2
12
0
0
0
Returns: 1
12
2
2
0
Returns: 2
100
99
3
0
Returns: 34
10
5
1
0
Returns: 6
1
100000
1
0
Returns: 99999
10
4
0
0
Returns: -1
0
65
5
10
Returns: 5
3
4
0
1
Returns: -1
100
5
1
0
Returns: 6
0
10000000000000000
1
1
Returns: 10000000000000000
1
10
0
0
Returns: -1
1
5
3
0
Returns: -1
100
10
1
0
Returns: 11
0
1000000000000000000
1
2
Returns: 83
700
1
1
0
Returns: 2
3
123
0
1
Returns: -1
7
8
2
0
Returns: 5
5
10
2
0
Returns: 6
423432
10
5
0
Returns: 3
100
1000
3
0
Returns: 300
17
15
5
0
Returns: 4
0
0
5
1
Returns: 0
6
3
3
0
Returns: 2
2
1024
0
2
Returns: 9
50
0
0
0
Returns: 1
1007
99999999
0
2
Returns: -1
0
624
2
10
Returns: 8
0
1000000000000000000
1
1
Returns: 1000000000000000000
10
5
5
0
Returns: 2
1007
99999999
0
0
Returns: -1
40
20
1
0
Returns: 21
0
1
0
1
Returns: -1
0
1000
0
2
Returns: -1
0
1000000
1
13
Returns: 21
10
0
0
0
Returns: 1
0
1
1
2
Returns: 1
2
8
0
2
Returns: 2
7
8
0
1
Returns: -1
12
0
0
41
Returns: -1
0
1000000000000000000
100
100
Returns: 9
0
123
0
41
Returns: -1
23
65
0
0
Returns: -1