Problema
n! = 1 × 2 × ... × n crece más rápido que cualquier potencia: 25! ya tiene 26 cifras. Calcula n! de forma exacta y suma sus cifras. Si no tienes enteros de precisión arbitraria, guarda el número como un arreglo de cifras y multiplícalo sucesivamente por 2, 3, ..., n.
Implementa factorial_digit_sum(n).
Entrada
n: el número del que se calcula el factorial.
Salida
Devuelve la suma de las cifras decimales de n!. Ten en cuenta que 0! = 1.
Restricciones
0 ≤ n ≤ 1000
Ejemplos
Entrada:
n = 5
Salida esperada:
expected = 3
Entrada:
long long n = 5;
Salida esperada:
long long expected = 3;
Entrada:
long n = 5;
Salida esperada:
long expected = 3;
Explicación
5! = 120 y 1 + 2 + 0 = 3.
Entrada:
n = 0
Salida esperada:
expected = 1
Entrada:
long long n = 0;
Salida esperada:
long long expected = 1;
Entrada:
long n = 0;
Salida esperada:
long expected = 1;
Explicación
0! vale 1 por definición, así que la respuesta es 1.
Cómo abordarlo
Inténtalo primero por tu cuenta y luego abre las pistas una a una.
Pista 1
Empieza en 1 y multiplica por 2, 3, ..., n.
Pista 2
Multiplica cada cifra, suma el acarreo, quédate con la última cifra y lleva el resto.
Pista 3
Si al final todavía queda acarreo, se convierte en nuevas cifras.
Complejidad esperada
tiempo O(n × D), donde D es la cantidad de cifras de n!, espacio extra O(D)
Referencias
Este reto está adaptado para CodeUtility. Sigue el enunciado y las restricciones indicadas arriba.