Problem Statement
A positive integer is K-smooth if each pair of its consecutive digits differs by at most K.
For example:
- 7, 77, and 333 are all 0-smooth while 12 and 20 are not.
- 7, 77, 234, 1010, 4323, and 556566765454 are all 1-smooth while 42, 90, and 54222 are not.
- 7, 42, 1357, 86420, and 865454321001 are all 2-smooth while 36, 204, and 9090 are not.
Count all K-smooth integers that lie between A and B, inclusive, and are multiples of C.
Definition
- Class:
- SmoothMultiples
- Method:
- count
- Parameters:
- int, long, long, long
- Returns:
- long
- Method signature:
- long count(int K, long A, long B, long C)
- (be sure your method is public)
Constraints
- K will be between 0 and 9, inclusive.
- A will be between 1 and 10^11 - 1, inclusive.
- B will be between A and 10^11 - 1, inclusive.
- C will be between 1 and 10^11 - 1, inclusive.
Examples
1
10
33
1
Returns: 8
We are counting all 1-smooth integers in the range [10,33]. There are eight of them: 10, 11, 12, 21, 22, 23, 32, and 33.
1
97
102
1
Returns: 4
The 1-smooth integers in this range are 98, 99, 100, and 101.
1
97
102
2
Returns: 2
The even 1-smooth integers in this range are 98 and 102.
9
123
45678
3
Returns: 15186
All positive integers are 9-smooth. There are 15,186 multiples of three in the given range.
3
1234
5678
73
Returns: 13
These are the 13 numbers: 1241, 1314, 2336, 2555, 3212, 3358, 3431, 3577, 4234, 4453, 4745, 5256, and 5475.
7
1234567
98765432100
2499
Returns: 23097617
23097617
0
123
4567
1
Returns: 12
These are the 12 numbers: 222, 333, ..., 999, 1111, 2222, 3333, and 4444.
7
1124125
98765432100
17
Returns: 3395490612
0
4718803
255999072
1
Returns: 16
0
116202
36299769
3
Returns: 12
0
128654
1945526
5
Returns: 1
0
56300
398384431
8
Returns: 4
0
2507971
58787800191
27
Returns: 3
0
1310277910
55499601715
54
Returns: 0
0
1744200488
19608173632
114
Returns: 0
0
94494
33064496
192
Returns: 0
0
1193
276590639
294
Returns: 0
0
255986
232351988
545
Returns: 0
0
7815141
1500396267
1285
Returns: 0
0
81
247443
2049
Returns: 0
0
3
27
4437
Returns: 0
0
348
11026628440
9401
Returns: 0
0
2664
20903991059
24068
Returns: 0
0
51
133
36299
Returns: 0
0
41106422055
48566053623
129925
Returns: 0
0
233
2316021
240555
Returns: 0
0
6734477
77909212440
323520
Returns: 0
0
1
99999999999
10
Returns: 0
8
3
81459717906
6
Returns: 11466150002
9
19
1897738583
103
Returns: 18424646
7
75
3607615
1003
Returns: 2662
1
3
1007038816
102
Returns: 700
2
1890
4183939
5
Returns: 10122
3
31513
75198252
3677
Returns: 716
1
58
33531870
20
Returns: 298
8
129166
2536895
54
Returns: 40715
1
39011912
8457999347
1240
Returns: 25
4
684
2375
40
Returns: 16
7
5215992
106686299
5
Returns: 13426234
9
52
425
6770
Returns: 0
1
106
120
679
Returns: 0
5
4
17
5857
Returns: 0
6
7761
10630210
8
Returns: 692456
7
7514
9877000
31
Returns: 232153
5
21
11918
6526
Returns: 1
1
131
93454
3
Returns: 292
1
4
32347735
4831
Returns: 3
5
25
5789029456
15
Returns: 72333297
8
111751646
117239125
112
Returns: 45459
7
2
3259
1
Returns: 2830
7
896
123887855
17
Returns: 4942012
4
16
318
1322
Returns: 0
4
166
516071
6
Returns: 19535
3
77
958186782
1
Returns: 19145986
6
1105
131657817
881
Returns: 67862
2
693
23801956402
7394
Returns: 2554
1
1775510286
51860222747
81
Returns: 3774
9
193
233175
6
Returns: 38830
4
8129
2480093158
117
Returns: 1443392
5
11853
29951
52
Returns: 147
8
10116
18329
24
Returns: 332
8
429136
6489961925
6056
Returns: 944158
1
3
6908
2691
Returns: 0
8
17
64707523
24
Returns: 2465600
7
346592
2012655
3
Returns: 398947
1
593677405
65438415283
40
Returns: 2394
7
35776
368933862
1512
Returns: 158969
5
5474968250
68084259645
381
Returns: 25231741
8
1245881
1501688
340
Returns: 711
2
2276
284148
60
Returns: 126
5
102
8150
3
Returns: 1580
4
258713
181000599
7770
Returns: 2139
1
12538631
45571348
2781
Returns: 3
1
13355
17808
2772
Returns: 0
9
414939
1006793
899
Returns: 658
7
55050855
15291095173
301
Returns: 30998716
7
1
48213
3492
Returns: 11
6
63
102315
8977
Returns: 7
5
3673
3147267958
100
Returns: 5183419
5
50
912
92
Returns: 5
4
89
3793551416
1
Returns: 252809422
6
53
80086716
7574
Returns: 5093
3
7
775744651
470
Returns: 22179
6
1
20372891601
11
Returns: 621050741
1
14656705
91304773109
440
Returns: 556
1
690
25856114
108
Returns: 101
5
1
31214185297
884
Returns: 5161316
3
2
14
10
Returns: 1
9
15
64325
6820
Returns: 9
1
1621
15642516612
1900
Returns: 222
7
4
9
4358
Returns: 0
9
3182591
1671268135
78
Returns: 21385712
6
251689
1093174410
194
Returns: 2310452
6
594751008
2288236845
5
Returns: 115886798
9
852
228856
329
Returns: 693
7
118
109738238
308
Returns: 237800
2
3631
8661
72
Returns: 6
9
172
1111219426
14
Returns: 79372804
3
23
71027114
56144
Returns: 47
5
4458
570994
14221825046
Returns: 0
7
13
11285627315
23474852419
Returns: 0
5
1
131557444
3804181
Returns: 11
2
26
12446
2603431
Returns: 0
3
101496
1454675006
1141831
Returns: 16
4
19
193843
2021248347
Returns: 0
3
1204
14513341
2076378135
Returns: 0
6
325408
495620524
48562
Returns: 4416
1
1092
3210618904
4459985001
Returns: 0
5
157
469
22259
Returns: 0
3
1
1611233
7984161245
Returns: 0
9
374329
3122108
695933211
Returns: 0
9
37
7513331
7973993252
Returns: 0
3
22
1951
14811942
Returns: 0
4
4556
2450204364
60965465809
Returns: 0
1
457
12279434
125955
Returns: 0
7
5
132028117
7137318
Returns: 12
3
3
8
86327405
Returns: 0
8
348
2691640199
116796315
Returns: 21
1
1
13151
15508215691
Returns: 0
3
2972
1260736
36773214
Returns: 0
6
289346930
75733295062
2981937
Returns: 8774
6
1
23306
3081227
Returns: 0
7
9
470
1811088
Returns: 0
8
2874131338
4129919285
15656345
Returns: 66
3
73340107
13869681543
6747111
Returns: 32
4
9697
1599043021
3767350642
Returns: 0
4
1569866
2248844689
36278535
Returns: 9
9
24
8048921
111841
Returns: 71
5
7
820817
14894010
Returns: 0
8
102656
37457692237
1620219054
Returns: 19
9
7336
130019955
2561663278
Returns: 0
9
392
73315270117
1528514969
Returns: 47
3
21
22
11208
Returns: 0
4
36119140
65059614
22203567945
Returns: 0
9
252231
486730782
32299
Returns: 15062
4
87889
706243
45149079311
Returns: 0
4
35
442084
943718
Returns: 0
8
51
424231
2660722719
Returns: 0
6
376201267
14296557416
8435691396
Returns: 0
7
2642778
11950973
258300
Returns: 18
5
2716
5852
16062
Returns: 0
6
158
55016587
68052327
Returns: 0
1
2013
7281
34093
Returns: 0
4
29
93788084
20887
Returns: 500
8
606795
43282288895
9355946129
Returns: 4
4
75671
7303251
52820
Returns: 16
6
1105
713098107
8233805782
Returns: 0
9
177081
164263587
23114593
Returns: 7
4
579
36349853
14311823
Returns: 0
7
293251
501758321
25308750720
Returns: 0
1
1026669
25556109315
7620716115
Returns: 0
3
11770
2452105
1014513161
Returns: 0
1
7
759161484
231038258
Returns: 0
3
479324
896470866
27255372
Returns: 1
7
764
270090445
1257011
Returns: 139
6
1
6332
22535237921
Returns: 0
1
12
511
9877179682
Returns: 0
8
14958578
186511978
735097630
Returns: 0
9
3
99999999995
1
Returns: 99999999993
8
255999072
91511168161
6
Returns: 12712804695
7
2507971
90841741944
24
Returns: 2181545911
8
8945303
97738975521
2
Returns: 40927328947
6
183614149
95202771888
306
Returns: 102670590
7
83289554753
99176884242
27
Returns: 316023087
6
5
94383965928
858
Returns: 36335367
6
133
92671677003
3
Returns: 10208714875
8
519151
94150306578
190
Returns: 383316929
8
561131087
91422105126
122
Returns: 622390237
8
137306
98330936967
6
Returns: 13727496409
8
19074554
96623926256
125
Returns: 676434458
7
103
97691369345
75
Returns: 811443073
7
9231579
97490315960
102
Returns: 558320415
7
4183939
95024028920
5
Returns: 10635247634
7
31
99369307143
11
Returns: 5270780685
8
33531870
91983085133
58
Returns: 1325497126
7
318753615
92651229201
20
Returns: 2288098992
7
2536895
98468183369
41
Returns: 1402973844
8
40
92211818923
234
Returns: 329487079
8
5
99856412540
425
Returns: 199483694
8
6180981859
98229226434
2
Returns: 38477788932
6
14
98455329979
106
Returns: 308625842
8
2883476
93913807842
679
Returns: 115706344
8
17
97619710177
359
Returns: 227737904
7
81979605
98436761456
8
Returns: 7033943089
8
13265930331
91688417412
31
Returns: 2109769994
6
1443
91145921960
3
Returns: 10208714529
7
4
93400548653
49
Returns: 1108989689
6
5789029456
98105255046
15
Returns: 1951151068
6
117239125
96285301388
2
Returns: 15943250842
9
42
99999999999
65534
Returns: 1525925
3
99999999999
99999999999
999999
Returns: 0
8
1
99999999999
5090013001
Returns: 12
3
1
9999999999
320000
Returns: 865
9
20000000
200000000
2000000
Returns: 91
1
97531
97531
97531
Returns: 0