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
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".
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.