Connection Status:
Competition Arena > ExtendedHappyNumbers

ExtendedHappyNumbers

SRM 334 · 2007-01-13 · by Andrew_Lazarev

SRM 334 · 2007-01-13 · by Andrew_Lazarev · Dynamic Programming, Math
Class Name: ExtendedHappyNumbers
Return Type: long
Method Name: calcTheSum
Arg Types: (int, int, int)
Problem Statement

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.

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)
72637
74236
5
Returns: 11789917

Submissions are judged against all 110 archived test cases, of which 5 are shown here. Case numbers match the judge’s.

Coding Area

Language: C++17 · define a public class ExtendedHappyNumbers with a public method long long calcTheSum(int A, int B, int K) · 110 test cases · 2 s / 256 MB per case

Submitting as anonymous