Alle Herausforderungen
Einfach 0 gelöst 0% Erfolgsquote

Quersumme einer Fakultät

Berechne die Quersumme von n Fakultät.

Das lernst du

  • Ein Ziffern-Array mit einer kleinen Zahl multiplizieren
  • Die Quersumme einer großen Zahl bilden
  • Daran denken, dass 0! = 1 ist

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

Beispiel 1
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.

Beispiel 2
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.

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.