Problem Statement
Dave writes the numbers from M to N (inclusive) on a piece of paper in base B (see notes for details). Then he hands the paper to Earl and asks Earl to compute the sum of the numbers. Earl, however, mistakenly assumes the numbers are written in base B+1. Return the value Earl will come up with.
For example, if M is 14, N is 18, and B is 3, Dave would write:112
120
121
122
200
Then Earl would sum the values (expressed here in base 10):
22
24
25
26
32
For a result of 129.
Definition
- Class:
- BaseConfusion
- Method:
- sum
- Parameters:
- int, int, int
- Returns:
- long
- Method signature:
- long sum(int M, int N, int B)
- (be sure your method is public)
Notes
- The number anan-1...a1a0 in base B corresponds to the value an*Bn + an-1*Bn-1 + ... + a1*B + a0. For example 120 in base 3 corresponds to the value 1 * 32 + 2 * 3 + 0 = 15 in decimal, while 120 in base 4 corresponds to the value 1 * 42 + 2 * 4 + 0 = 24 in decimal.
- When writing numbers in bases higher than 10, it may be necessary to represent digits higher than 9. In such cases letters (a, b, c, ...) are used to represent (10, 11, 12, ...) as needed.
- The return value is guaranteed to fit within a 64-bit signed integer datatype.
Constraints
- M and N will be between 1 and 350000000, inclusive.
- M will be less than or equal to N.
- B will be between 3 and 16, inclusive.
Examples
14
18
3
Returns: 129
The example from the problem statement.
1
10
16
Returns: 55
Earl produces the correct answer in this case.
100
100
10
Returns: 121
209881
210565
3
Returns: 3141592653
1
350000000
3
Returns: 7206282108986150421
1
350000000
16
Returns: 89827255572899906
1167
5237493
3
Returns: 552135969583654
1983
1201464
3
Returns: 19658318322265
24
1734
3
Returns: 7363614
1529
4637
4
Returns: 29735203
2
135093
4
Returns: 47965273958
428
36012284
4
Returns: 8393497735422769
20
4586
5
Returns: 23128709
1
5710
5
Returns: 36433310
1901
5840
5
Returns: 34646408
334
4294005
6
Returns: 29753971547148
226
6073
6
Returns: 32971166
103
9066929
6
Returns: 136893788009663
1723661
7062232
7
Returns: 61658763129315
7595
53449938
7
Returns: 4314064544592466
5
3533
7
Returns: 9773021
139
63850
8
Returns: 3443322041
49
1337472
8
Returns: 1769540471211
5687
237509809
8
Returns: 76181910936062528
229
656
9
Returns: 231492
524690
14844808
9
Returns: 222114366802583
27101
1597142
9
Returns: 2310830562586
1
242056
10
Returns: 45411371427
44
179506
10
Returns: 24621572853
10243
5898221
10
Returns: 30300288194285
184
2303
11
Returns: 3263701
44
11886
11
Returns: 90789629
1906
1007710
11
Returns: 773405576064
3740
36665697
12
Returns: 1083345418865487
6105
4128167
12
Returns: 13075438231203
153
48794
12
Returns: 1586844588
552
81313
13
Returns: 4331441245
2
142
13
Returns: 10867
29961
95831
13
Returns: 5482413782
6957
5617022
14
Returns: 22125019300104
245
6464
14
Returns: 24959653
21211
187826
14
Returns: 22638099384
234
4849
15
Returns: 13686970
2
2
15
Returns: 2
1304
1162792
15
Returns: 899064536802
48
8109897
16
Returns: 44177991983349
5
69153
16
Returns: 2875267897
2231
110353
16
Returns: 7503972845
350000000
350000000
7
Returns: 1285245000
350000000
350000000
3
Returns: 43241330794
350000000
350000000
16
Returns: 526394562
175000000
350000000
3
Returns: 5605031007176540786
1
349999999
16
Returns: 89827255046505344
1
350000000
13
Returns: 101535017249312478
1
350000000
15
Returns: 93164804607389436
1
350000000
10
Returns: 127787124415512498
1
35000000
3
Returns: 40080340469042181
978
349000000
13
Returns: 100952409108362049
1
350000000
4
Returns: 1161729926164166125
1
350000000
7
Returns: 209503247552285152
1
350000000
12
Returns: 106361178626317725
2211212
222222222
13
Returns: 40634142653680584
2
349999992
3
Returns: 7206281763055504103
1
35000000
16
Returns: 855758329910067
1
350000000
11
Returns: 116914094803211776
1
35000000
10
Returns: 1161701177319318
1
100000000
3
Returns: 432417925054835484
1
350000000
8
Returns: 169017298599526732
200
350000000
13
Returns: 101535017249290704
17
349999999
12
Returns: 106361178017203135
2211212
350000000
3
Returns: 7206200588297572818
1
350000000
5
Returns: 481013419244366848
1
350000000
9
Returns: 140367624804501534
1
3500000
7
Returns: 15093633981040
349999999
350000000
3
Returns: 86482661587
2
34798322
15
Returns: 872635906694978