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

Somme de grands nombres

Additionner une liste de nombres trop longs pour n'importe quel type entier natif.

Ce que vous allez apprendre

  • Additionner des nombres stockés sous forme de chaînes de chiffres
  • Propager les retenues d'une colonne à l'autre
  • Supprimer les zéros en tête d'un résultat

Problème

Chaque nombre est donné sous forme de chaîne de chiffres décimaux et peut compter jusqu'à 60 chiffres, bien au-delà de ce que peut contenir un entier sur 64 bits. Additionnez-les tous et renvoyez le total exact. C'est l'addition posée de l'école : on additionne les chiffres en partant de la droite et on reporte la retenue sur la colonne suivante.

Implémentez sum_of_big_numbers(numbers).

Entrée

numbers : des entiers positifs ou nuls écrits sous forme de chaînes de chiffres, sans zéros en tête (zéro s'écrit "0").

Sortie

Renvoyez la somme exacte sous forme de chaîne de chiffres sans zéros en tête. La somme d'une liste vide vaut "0".

Contraintes

0 ≤ numbers.length ≤ 100 ; chaque nombre a de 1 à 60 chiffres

Exemples

Exemple 1
Entrée :
numbers = ["999", "1"]

Sortie attendue :
expected = "1000"
Entrée :
std::vector<std::string> numbers = {"999", "1"};

Sortie attendue :
std::string expected = "1000";
Entrée :
string[] numbers = new string[] {"999", "1"};

Sortie attendue :
string expected = "1000";

Explication

Ajouter 1 à 999 propage une retenue dans toutes les colonnes : "1000".

Exemple 2
Entrée :
numbers = ["98765432109876543210", "12345678901234567890"]

Sortie attendue :
expected = "111111111011111111100"
Entrée :
std::vector<std::string> numbers = {"98765432109876543210", "12345678901234567890"};

Sortie attendue :
std::string expected = "111111111011111111100";
Entrée :
string[] numbers = new string[] {"98765432109876543210", "12345678901234567890"};

Sortie attendue :
string expected = "111111111011111111100";

Explication

Colonne par colonne, les deux nombres de 20 chiffres donnent "111111111011111111100", qui a un chiffre de plus que chacun d'eux.

Comment l'aborder

Essayez d'abord seul, puis ouvrez les indices un par un.

Indice 1

Alignez les nombres sur leur dernier chiffre.

Indice 2

Additionnez une colonne à la fois en reportant la retenue sur la colonne suivante.

Indice 3

Une fois toutes les colonnes traitées, une retenue restante devient de nouveaux chiffres en tête.

Complexité attendue

temps O(total digits), proportionnel au nombre total de chiffres, espace supplémentaire O(max length), proportionnel à la plus grande longueur

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.