Problema
Ogni numero arriva come stringa di cifre decimali e può avere fino a 60 cifre, molto più di quanto possa contenere un intero a 64 bit. Sommali tutti e restituisci il totale esatto. È l'addizione in colonna che si impara a scuola: somma le cifre partendo da destra e porta il riporto nella colonna successiva.
Implementa sum_of_big_numbers(numbers).
Input
numbers: interi non negativi scritti come stringhe di cifre, senza zeri iniziali (lo zero è "0").
Output
Restituisci la somma esatta come stringa di cifre senza zeri iniziali. Una lista vuota ha somma "0".
Vincoli
0 ≤ numbers.length ≤ 100; ogni numero ha da 1 a 60 cifre
Esempi
Input:
numbers = ["999", "1"]
Output atteso:
expected = "1000"
Input:
std::vector<std::string> numbers = {"999", "1"};
Output atteso:
std::string expected = "1000";
Input:
string[] numbers = new string[] {"999", "1"};
Output atteso:
string expected = "1000";
Spiegazione
Sommando 1 a 999 il riporto attraversa tutte le colonne: "1000".
Input:
numbers = ["98765432109876543210", "12345678901234567890"]
Output atteso:
expected = "111111111011111111100"
Input:
std::vector<std::string> numbers = {"98765432109876543210", "12345678901234567890"};
Output atteso:
std::string expected = "111111111011111111100";
Input:
string[] numbers = new string[] {"98765432109876543210", "12345678901234567890"};
Output atteso:
string expected = "111111111011111111100";
Spiegazione
Colonna per colonna, i due numeri da 20 cifre danno "111111111011111111100", una cifra in più di ciascuno dei due.
Come affrontarlo
Prova prima da solo, poi apri un suggerimento alla volta.
Suggerimento 1
Allinea i numeri sull'ultima cifra.
Suggerimento 2
Somma una colonna alla volta, tenendo il riporto per la colonna successiva.
Suggerimento 3
Quando hai finito tutte le colonne, l'eventuale riporto rimasto diventa nuove cifre iniziali.
Complessità attesa
tempo O(total digits), spazio aggiuntivo O(max length), dove total digits è il numero totale di cifre e max length la lunghezza massima
Riferimenti
Questa sfida è adattata per CodeUtility. Segui la traccia e i vincoli sopra.