Alle Herausforderungen
Schwierig 0 gelöst 0% Erfolgsquote

Ketten aus Ziffernfakultäten

Zähle die Startzahlen, deren Kette aus Ziffernfakultäten genau eine vorgegebene Anzahl verschiedener Glieder hat.

Das lernst du

  • Einer Kette folgen, bis sich ein Wert wiederholt
  • Kettenlängen innerhalb und vor einer Schleife bestimmen
  • Gespeicherte Längen wiederverwenden

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

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 und 2! = 2, also werden 1 und 2 jeweils auf sich selbst abgebildet, ihre Ketten haben nur 1 Glied. Die Antwort ist 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 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.

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.