All challenges
Hard 0 solved 0% acceptance

Digit Factorial Chains

Count starting numbers whose digit factorial chain has exactly a given number of distinct terms.

What you'll learn

  • Follow a chain until a value repeats
  • Find chain lengths inside and before a loop
  • Reuse stored lengths

Problem

Replace a number by the sum of the factorials of its digits: 145 gives 1! + 4! + 5! = 145 again, and 69 gives 6! + 9! = 363600. Repeating this always falls into a loop. The chain of a start is its terms until the first repeat: 69, 363600, 1454, 169, 363601 and then 1454 again, so 69 has 5 distinct terms. Count the starting numbers from 1 to limit whose chain has exactly length distinct terms.

Implement digit_factorial_chains(limit, length).

Many chains run into the same numbers. Store each number's chain length once it is known and reuse it.

Input

limit: The largest starting number.

length: The number of distinct terms wanted, the start included.

Output

Return how many starting numbers n with 1 ≤ n ≤ limit have exactly length distinct terms in their chain.

Constraints

1 ≤ limit ≤ 100,000; 1 ≤ length ≤ 70

Examples

Example 1
Input:
limit = 2
length = 1

Expected output:
expected = 2
Input:
long long limit = 2;
long long length = 1;

Expected output:
long long expected = 2;
Input:
long limit = 2;
long length = 1;

Expected output:
long expected = 2;

Explanation

1! = 1 and 2! = 2, so 1 and 2 each map to themselves and have a chain of 1 term. The answer is 2.

Example 2
Input:
limit = 10
length = 2

Expected output:
expected = 1
Input:
long long limit = 10;
long long length = 2;

Expected output:
long long expected = 1;
Input:
long limit = 10;
long length = 2;

Expected output:
long expected = 1;

Explanation

3 gives 6, then 720, 5043, ... so it is long. 10 gives 1! + 0! = 2 and then 2 again: two terms. Only 10 has exactly 2, so the answer is 1.

How to approach it

Try on your own first, then open one hint at a time.

Hint 1

Precompute 0! to 9! once.

Hint 2

Record each value's step number in the current chain; a repeat tells you where the loop starts.

Hint 3

Values in the loop all have the loop's length, and each value before it has one more than the next.

Expected complexity

O(limit × log limit) time with memoization, O(limit) extra space

References

This challenge is adapted for CodeUtility. Follow the statement and constraints above.

The best passing solution of each coder. Faster, smaller and better-reviewed solutions rank higher.

No passing solutions yet. Solve it to take first place.

Learn from others

Community solutions

No published solutions yet. Solve this challenge to share the first one.