Problema
n! = 1 × 2 × ... × n cresce mais rápido que qualquer potência: 25! já tem 26 dígitos. Calcule n! exatamente e some os seus dígitos. Sem inteiros grandes, guarde o número como um array de dígitos e multiplique-o por 2, 3, ..., n, um de cada vez.
Implemente factorial_digit_sum(n).
Entrada
n: o número do qual se calcula o fatorial.
Saída
Retorne a soma dos dígitos decimais de n!. Observe que 0! = 1.
Restrições
0 ≤ n ≤ 1000
Exemplos
Entrada:
n = 5
Saída esperada:
expected = 3
Entrada:
long long n = 5;
Saída esperada:
long long expected = 3;
Entrada:
long n = 5;
Saída esperada:
long expected = 3;
Explicação
5! = 120 e 1 + 2 + 0 = 3.
Entrada:
n = 0
Saída esperada:
expected = 1
Entrada:
long long n = 0;
Saída esperada:
long long expected = 1;
Entrada:
long n = 0;
Saída esperada:
long expected = 1;
Explicação
Por definição, 0! é 1, então a resposta é 1.
Como abordar
Tente sozinho primeiro e depois abra uma dica de cada vez.
Dica 1
Comece com 1 e multiplique por 2, 3, ..., n.
Dica 2
Multiplique cada dígito, some o "vai um", fique com o último dígito e leve o resto adiante.
Dica 3
Se ainda sobrar "vai um" no final, ele vira novos dígitos.
Complexidade esperada
tempo O(n × D), em que D é a quantidade de dígitos de n!, espaço extra O(D)
Referências
Este desafio foi adaptado para o CodeUtility. Siga o enunciado e as restrições acima.