Problem
n! = 1 × 2 × ... × n wächst schneller als jede Potenz: 25! hat schon 26 Stellen. Berechne n! exakt und bilde die Quersumme. Ohne große Ganzzahlen speicherst du die Zahl als Array von Ziffern und multiplizierst sie nacheinander mit 2, 3, ..., n.
Implementiere factorial_digit_sum(n).
Eingabe
n: Die Zahl, deren Fakultät berechnet wird.
Ausgabe
Gib die Quersumme von n! zurück. Beachte, dass 0! = 1 ist.
Einschränkungen
0 ≤ n ≤ 1000
Beispiele
Eingabe:
n = 5
Erwartete Ausgabe:
expected = 3
Eingabe:
long long n = 5;
Erwartete Ausgabe:
long long expected = 3;
Eingabe:
long n = 5;
Erwartete Ausgabe:
long expected = 3;
Erläuterung
5! = 120 und 1 + 2 + 0 = 3.
Eingabe:
n = 0
Erwartete Ausgabe:
expected = 1
Eingabe:
long long n = 0;
Erwartete Ausgabe:
long long expected = 1;
Eingabe:
long n = 0;
Erwartete Ausgabe:
long expected = 1;
Erläuterung
0! ist per Definition 1, also lautet die Antwort 1.
So gehst du vor
Versuch es zuerst allein und öffne dann einen Hinweis nach dem anderen.
Hinweis 1
Beginne mit 1 und multipliziere mit 2, 3, ..., n.
Hinweis 2
Multipliziere jede Ziffer, addiere den Übertrag, behalte die letzte Stelle und trage den Rest weiter.
Hinweis 3
Bleibt am Ende noch ein Übertrag übrig, wird er zu neuen Ziffern.
Erwartete Komplexität
Zeit O(n × D), wobei D die Stellenzahl von n! ist, zusätzlicher Speicher O(D)
Referenzen
Diese Aufgabe wurde für CodeUtility angepasst. Beachte die oben genannten Vorgaben und Einschränkungen.