TopCoder problem "BaseConfusion" used in Member SRM 482 (Division II Level Three)



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

0)
    
14
18
3
Returns: 129
The example from the problem statement.
1)
    
1
10
16
Returns: 55
Earl produces the correct answer in this case.
2)
    
100
100
10
Returns: 121
3)
    
209881
210565
3
Returns: 3141592653

Problem url:

http://www.topcoder.com/stat?c=problem_statement&pm=10856

Problem stats url:

http://www.topcoder.com/tc?module=ProblemDetail&rd=14235&pm=10856

Writer:

pieguy

Testers:

ivan_metelsky , boba5551 , it4.kp , abal9002

Problem categories:

Math, Recursion