Problem
Ersetze eine Zahl durch die Summe der Fakultäten ihrer Ziffern: 145 ergibt 1! + 4! + 5! = 145, also wieder sich selbst, und 69 ergibt 6! + 9! = 363600. Wiederholt man das, landet man immer in einer Schleife. Die Kette einer Startzahl besteht aus ihren Gliedern bis zur ersten Wiederholung: 69, 363600, 1454, 169, 363601 und dann wieder 1454. Die 69 hat also 5 verschiedene Glieder. Zähle die Startzahlen von 1 bis limit, deren Kette genau length verschiedene Glieder hat.
Implementiere digit_factorial_chains(limit, length).
Viele Ketten laufen in dieselben Zahlen hinein. Speichere die Kettenlänge jeder Zahl, sobald du sie kennst, und verwende sie wieder.
Eingabe
limit: Die größte Startzahl.
length: Die gewünschte Anzahl verschiedener Glieder, die Startzahl eingeschlossen.
Ausgabe
Gib zurück, wie viele Startzahlen n mit 1 ≤ n ≤ limit genau length verschiedene Glieder in ihrer Kette haben.
Einschränkungen
1 ≤ limit ≤ 100.000; 1 ≤ length ≤ 70
Beispiele
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 und 2! = 2, also werden 1 und 2 jeweils auf sich selbst abgebildet, ihre Ketten haben nur 1 Glied. Die Antwort ist 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 ergibt 6, dann 720, 5043, ..., diese Kette ist also lang. 10 ergibt 1! + 0! = 2 und dann wieder 2, also zwei Glieder. Nur 10 hat genau 2, also lautet die Antwort 1.
So gehst du vor
Versuch es zuerst allein und öffne dann einen Hinweis nach dem anderen.
Hinweis 1
Berechne 0! bis 9! einmal im Voraus.
Hinweis 2
Notiere für jeden Wert seine Schrittnummer in der aktuellen Kette. Eine Wiederholung zeigt dir, wo die Schleife beginnt.
Hinweis 3
Alle Werte in der Schleife haben die Länge der Schleife, und jeder Wert davor hat eins mehr als sein Nachfolger.
Erwartete Komplexität
Zeit O(limit × log limit) mit Memoisierung, zusätzlicher Speicher O(limit)
Referenzen
Diese Aufgabe wurde für CodeUtility angepasst. Beachte die oben genannten Vorgaben und Einschränkungen.