Problema
n! = 1 × 2 × ... × n cresce più in fretta di qualsiasi potenza: 25! ha già 26 cifre. Calcola n! in modo esatto e somma le sue cifre. Senza interi grandi, memorizza il numero in un array di cifre e moltiplicalo via via per 2, 3, ..., n.
Implementa factorial_digit_sum(n).
Input
n: il numero di cui calcolare il fattoriale.
Output
Restituisci la somma delle cifre decimali di n!. Ricorda che 0! = 1.
Vincoli
0 ≤ n ≤ 1000
Esempi
Input:
n = 5
Output atteso:
expected = 3
Input:
long long n = 5;
Output atteso:
long long expected = 3;
Input:
long n = 5;
Output atteso:
long expected = 3;
Spiegazione
5! = 120 e 1 + 2 + 0 = 3.
Input:
n = 0
Output atteso:
expected = 1
Input:
long long n = 0;
Output atteso:
long long expected = 1;
Input:
long n = 0;
Output atteso:
long expected = 1;
Spiegazione
Per definizione 0! vale 1, quindi la risposta è 1.
Come affrontarlo
Prova prima da solo, poi apri un suggerimento alla volta.
Suggerimento 1
Parti da 1 e moltiplica per 2, 3, ..., n.
Suggerimento 2
Moltiplica ogni cifra, aggiungi il riporto, tieni l'ultima cifra e riporta il resto.
Suggerimento 3
Se alla fine resta un riporto, diventa nuove cifre.
Complessità attesa
tempo O(n × D), dove D è il numero di cifre di n!, spazio aggiuntivo O(D)
Riferimenti
Questa sfida è adattata per CodeUtility. Segui la traccia e i vincoli sopra.