Tous les défis
Facile 0 résolus 0 % de réussite

Somme des chiffres d'une factorielle

Additionner les chiffres décimaux de factorielle n.

Ce que vous allez apprendre

  • Multiplier un tableau de chiffres par un petit nombre
  • Additionner les chiffres d'un grand nombre
  • Se souvenir que 0! = 1

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

Exemple 1
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.

Exemple 2
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.

La meilleure solution validée de chaque codeur. Les plus rapides, les plus légères et les mieux notées passent devant.

Aucune solution validée pour l'instant. Résolvez-le et prenez la première place.

Apprenez des autres

Solutions de la communauté

Aucune solution publiée pour l'instant. Résolvez ce défi pour partager la première.