Alle Herausforderungen
Schwierig 0 gelöst 0% Erfolgsquote

Digit Factorial Chains

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

Das lernst du

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

Problem

Übersetzung anzeigen

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.

Einschränkungen

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

Beispiele

Beispiel 1
Eingabe:
limit = 2
length = 1

Erwartete Ausgabe:
expected = 2
Eingabe:
long long limit = 2;
long long length = 1;

Erwartete Ausgabe:
long long expected = 2;
Eingabe:
long limit = 2;
long length = 1;

Erwartete Ausgabe:
long expected = 2;

Erläuterung

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

Beispiel 2
Eingabe:
limit = 10
length = 2

Erwartete Ausgabe:
expected = 1
Eingabe:
long long limit = 10;
long long length = 2;

Erwartete Ausgabe:
long long expected = 1;
Eingabe:
long limit = 10;
long length = 2;

Erwartete Ausgabe:
long expected = 1;

Erläuterung

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.

So gehst du vor

Versuch es zuerst allein und öffne dann einen Hinweis nach dem anderen.

Hinweis 1

Precompute 0! to 9! once.

Hinweis 2

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

Hinweis 3

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

Erwartete Komplexität

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

Referenzen

Diese Aufgabe wurde für CodeUtility angepasst. Beachte die oben genannten Vorgaben und Einschränkungen.

Die beste bestandene Lösung jedes Coders. Schnellere, sparsamere und besser bewertete Lösungen stehen weiter oben.

Noch keine bestandene Lösung. Löse sie und hol dir Platz eins.

Von anderen lernen

Community-Lösungen

Noch keine veröffentlichten Lösungen. Löse die Aufgabe und teile als Erster eine Lösung.