Problem Statement
Take all the positive integers from A to B, inclusive.
Reverse as many of them as you like. (E.g., reversing 1234 changes it into 4321, and reversing 4700 turns it into 0074 = 74.)
Then, add them all up.
Calculate the largest possible result you can get. Return that result modulo (10^9 + 7).
Definition
- Class:
- NumReverseHard
- Method:
- getsum
- Parameters:
- long, long
- Returns:
- int
- Method signature:
- int getsum(long A, long B)
- (be sure your method is public)
Constraints
- B will be between 1 and 10^18 - 1, inclusive.
- A will be between 1 and B, inclusive.
Examples
21
23
Returns: 75
We have the numbers 21, 22, and 23. We can reverse 23 to get 32. This will give us the final sum 21 + 22 + 32 = 75, which is the largest result we can get from these three numbers.
12
21
Returns: 489
Note that after we reverse 12, our collection of numbers will contain two separate 21s. Each of them contributes to the final sum.
97
101
Returns: 495
Here an optimal solution is not to reverse anything.
123
128
Returns: 3426
Here an optimal strategy is to reverse everything.
89
234
Returns: 67841
100000000000000000
100000000000000000
Returns: 300000007
The only number is 10^17. The optimal strategy is not to reverse it (as reversing it changes its value to 1). Thus, the optimal sum is 10^17 and the correct return value is that modulo 10^9 + 7.
476
6495899089
Returns: 947452968
1
1844864785
Returns: 109579851
1145175955
1149502749
Returns: 485205786
784
8135212
Returns: 429647260
78435
221263
Returns: 206773283
445
12564
Returns: 191507718
4
103
Returns: 6727
3793
685712084503910
Returns: 915677000
108
262891543798
Returns: 381992265
13157
43892
Returns: 673938405
1638747516
16288652856818
Returns: 201995170
185
11433032
Returns: 837509164
1
7532073
Returns: 209659964
14
336
Returns: 127769
606
1314
Returns: 1894128
22
59943
Returns: 916369517
5
7693
Returns: 41631714
32
6837
Returns: 35086502
30232
18921607123
Returns: 959352063
6
289
Returns: 103558
8
552
Returns: 257630
5
41109
Returns: 731577783
823278
965627896036
Returns: 860320374
1
6509
Returns: 32721069
24
66595347
Returns: 696064712
902
15062
Returns: 318525215
3335
490724826
Returns: 970193497
165749267
300306665
Returns: 802441946
8844905366
969763096245
Returns: 671911640
11025888
24805978
Returns: 469258415
548
2171226128377415
Returns: 902199484
6923058137
165878488098
Returns: 99394356
261366086
1465411756
Returns: 551091371
52
173
Returns: 39150
3889
66768945
Returns: 146175956
3
6448411
Returns: 22292348
5677503
5695941
Returns: 11716844
1
281
Returns: 98517
97
7151992
Returns: 158345724
654295508
1579906781387810
Returns: 416891172
934325
40725224496
Returns: 203191256
3236
364059861
Returns: 713111536
19
3397
Returns: 13217851
799596077
930708888
Returns: 435588113
193215222728510
832949477495608489
Returns: 148935671
91
97
Returns: 658
225301
7333945
Returns: 597669860
3
4539
Returns: 19831647
174
255
Returns: 42438
1
3893227
Returns: 650875671
17
154
Returns: 31158
126
133609434
Returns: 615739886
409205
795331
Returns: 490785862
436577
486669
Returns: 390068252
15146
79070
Returns: 14400045
315
4620
Returns: 20206437
25
2109090725
Returns: 89326445
40336
240186
Returns: 772690921
1
3357021040
Returns: 29785222
2349
33475978
Returns: 592449230
3
133
Returns: 20977
5
13
Returns: 108
2
520306036143
Returns: 858642871
8
3268056
Returns: 7891241
2645293603699
99034588024617343
Returns: 776950956
19
1946298995922863
Returns: 660611085
12509774677372
143580130706641
Returns: 591129630
45996617
381849621
Returns: 667946965
157
1907349848
Returns: 933913108
4103285419904
277154190158675813
Returns: 876125929
410703148368
7669261306861935
Returns: 258766933
4090
3023842344
Returns: 216413381
27866590
3294176569958
Returns: 176613242
7
75588914
Returns: 743714708
7074
77158176997
Returns: 736606756
105141228013
106918919451516
Returns: 6191612
1459162
1255502558154366
Returns: 569256789
20
31421756757
Returns: 981731025
56345925
211109456
Returns: 82881170
30
441
Returns: 187620
1185452
2375759
Returns: 264267857
183633072
2183041391050153
Returns: 228900425
21
18568082
Returns: 222490637
3156
8878527296414037
Returns: 189841049
16355083833
372045891551
Returns: 266531593
592838937347
17529479520781
Returns: 945117460
433523059529
900839281627
Returns: 823585529
32
12328470606880
Returns: 723453259
23970232
209107862
Returns: 401326736
1485282
3692102784026295
Returns: 266868922
20254
9444452725468401
Returns: 428824383
23
701344464057002
Returns: 471121806
77593231
25176049749275093
Returns: 758498798
1909
1698785
Returns: 644475542
152495
86665357457
Returns: 763790657
5408
511904
Returns: 340457627
53371
407295902057884
Returns: 457011327
38
37163664973817351
Returns: 82584582
12001660
223628464
Returns: 228735428
8
92770339553046
Returns: 565826205
14339445167789525
468243742410348600
Returns: 117201290
51873266
3942794915399
Returns: 372589379
206
139532
Returns: 274846918
2286029414
143193910098
Returns: 233362613
3660599072
737096550558751
Returns: 350562113
2855527
32229362812505481
Returns: 483931252
12130589768
1247674258908801
Returns: 375855252
3410359265823
1059222854165046
Returns: 33998713
467159575
999293832615381
Returns: 712698496
40297
51998
Returns: 710401797
107
243139738615312
Returns: 365933148
2780036
9501201114964956
Returns: 533437289
10676395752
30742114816217561
Returns: 559828552
7120
61833221501
Returns: 190268282
39
277949484299567881
Returns: 942747542
56288187674534293
128308278193691855
Returns: 32632313
1809552
3839023358972
Returns: 508846166
894496949
6228186735554391
Returns: 91888880
83
1578
Returns: 3533657
4276417061
176601744536
Returns: 154802618
226850461955495071
779691498663827129
Returns: 607303
488038841218545464
556451472049352993
Returns: 8875603
290900747408519035
775399346746941309
Returns: 25741780
436261700841551226
441345874549282887
Returns: 845354209
610096279795852872
923038084289080419
Returns: 243355642
816420489154312984
901365509133572219
Returns: 333959194
16864657971502813
992527423527948984
Returns: 263805152
83204766387570012
933191293051761537
Returns: 189283608
480786517171949368
865212091581208622
Returns: 5595402
197875116999659091
809050162799454265
Returns: 874092411
242296191361850470
509831404774146487
Returns: 173439504
443961584857402266
911411030112186125
Returns: 76848750
143561430509412247
971654155492045598
Returns: 451261568
325831620326063803
750106225512429737
Returns: 934765766
31904185568548957
575716028440144648
Returns: 151668324
233985067296750778
502901959838845688
Returns: 87685442
119694171613872234
482161646661672048
Returns: 548890240
510986111204506995
755770829770562521
Returns: 120559157
366842948122695750
528323516008266891
Returns: 863195101
511944122076602218
924330822767353054
Returns: 919084522
456666645678
6666798456781
Returns: 229271216
3941696087409430
894569703897342045
Returns: 651210649