Problème
n! = 1 × 2 × ... × n croît plus vite que n'importe quelle puissance : 25! a déjà 26 chiffres. Calculez n! exactement et additionnez ses chiffres. Sans grands entiers, stockez le nombre dans un tableau de chiffres et multipliez-le successivement par 2, 3, ..., n.
Implémentez factorial_digit_sum(n).
Entrée
n : le nombre dont on prend la factorielle.
Sortie
Renvoyez la somme des chiffres décimaux de n!. Rappel : 0! = 1.
Contraintes
0 ≤ n ≤ 1000
Exemples
Entrée :
n = 5
Sortie attendue :
expected = 3
Entrée :
long long n = 5;
Sortie attendue :
long long expected = 3;
Entrée :
long n = 5;
Sortie attendue :
long expected = 3;
Explication
5! = 120 et 1 + 2 + 0 = 3.
Entrée :
n = 0
Sortie attendue :
expected = 1
Entrée :
long long n = 0;
Sortie attendue :
long long expected = 1;
Entrée :
long n = 0;
Sortie attendue :
long expected = 1;
Explication
0! vaut 1 par définition, donc la réponse est 1.
Comment l'aborder
Essayez d'abord seul, puis ouvrez les indices un par un.
Indice 1
Partez de 1 et multipliez par 2, 3, ..., n.
Indice 2
Multipliez chaque chiffre, ajoutez la retenue, gardez le chiffre des unités et reportez le reste.
Indice 3
S'il reste une retenue à la fin, elle devient de nouveaux chiffres.
Complexité attendue
temps O(n × D), où D est le nombre de chiffres de n!, espace supplémentaire O(D)
Références
Ce défi a été adapté pour CodeUtility. Suivez l'énoncé et les contraintes ci-dessus.