TopCoder problem "ExtendedHappyNumbers" used in SRM 334 (Division I Level Two , Division II Level Three)



Problem Statement

    

Given a positive integer N, raise each of its digits to the K-th power and sum those values to get SK(N). For example, S2(65) = 62 + 52 = 61. Now, consider a sequence N, SK(N), SK(SK(N)) and so on. The happiness of N with respect to K is the smallest number in this sequence.

You will be given three ints A, B and K. Calculate the happiness of each integer between A and B, inclusive, with respect to K and return their sum.

 

Definition

    
Class:ExtendedHappyNumbers
Method:calcTheSum
Parameters:int, int, int
Returns:long
Method signature:long calcTheSum(int A, int B, int K)
(be sure your method is public)
    
 

Constraints

-A will be between 1 and 1,000,000, inclusive.
-B will be between A and 1,000,000, inclusive.
-K will be between 1 and 6, inclusive.
 

Examples

0)
    
13
13
2
Returns: 1
The sequence for 13 is 13, 10, 1, 1...
1)
    
1
5
2
Returns: 14
The sequences for numbers 1 to 5 are:

1: 1, 1, 1...

2: 2, 4, 16, 37, 58, 89, 145, 42, 20, 4...

3: 3, 9, 81, 65, 61, 37, 58, 89, 145, 42, 20, 4, 16, 37...

4: 4, 16, 37, 58, 89, 145, 42, 20, 4...

5: 5, 25, 29, 85, 89, 145, 42, 20, 4, 16, 37, 58, 89...

2)
    
10
99
1
Returns: 450
3)
    
535
538
3
Returns: 820
4)
    
100000
400000
6
Returns: 5169721292

Problem url:

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

Problem stats url:

http://www.topcoder.com/tc?module=ProblemDetail&rd=10658&pm=7244

Writer:

Andrew_Lazarev

Testers:

PabloGilberto , brett1479 , Olexiy , marian

Problem categories:

Dynamic Programming, Math