Einfach 0 gelöst 0% Erfolgsquote

Factorial Digit Sum

Add up the decimal digits of n factorial.

Das lernst du

  • Multiply a digit array by a small number
  • Sum the digits of a large number
  • Remember that 0! = 1

Problem

Übersetzung anzeigen

n! = 1 × 2 × ... × n grows faster than any power: 25! already has 26 digits. Compute n! exactly and add up its digits. Without big integers, store the number as an array of digits and multiply it by 2, 3, ..., n in turn.

Implement factorial_digit_sum(n).

Input

n: The number whose factorial is taken.

Output

Return the sum of the decimal digits of n!. Note that 0! = 1.

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 and 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! is 1 by definition, so the answer is 1.

So gehst du vor

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

Hinweis 1

Start from 1 and multiply by 2, 3, ..., n.

Hinweis 2

Multiply each digit, add the carry, keep the last digit and carry the rest.

Hinweis 3

When the carry is still left over at the end, it becomes new digits.

Erwartete Komplexität

O(n × D) time where D is the digit count of n!, O(D) 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.