Adunarea numerelor mari — cifră cu cifră, cu transport

De ce contează?

Aduni două sume de bani pe coloane, pe hârtie. Începi de la coloana unităților, din dreapta. Când unitățile dau peste 9, scrii doar cifra de la urmă și treci un mic „1” deasupra coloanei următoare — transportul. Apoi aduni coloana zecilor împreună cu acel „1”. Calculatorul face exact la fel, doar că ține cifrele într-un vector.

Ideea: adunare ca pe hârtie, de la unități

Reamintim convenția capitolului: un număr mare e un vector<int> în care cifra unităților stă pe indexul 0 (reprezentare inversată, little-endian). Am ales asta tocmai pentru adunare: pornim de la unități și transportul curge dinspre index mic spre index mare, adică în sensul în care parcurgem vectorul.

La fiecare poziție i adunăm cifra primului număr, cifra celui de-al doilea și transportul rămas: suma = a[i] + b[i] + carry. Din suma scoatem cifra de scris cu suma % 10 și noul transport cu suma / 10. Dacă un număr s-a terminat (e mai scurt), considerăm cifra lipsă egală cu 0.

Exemplu pas cu pas

Adunăm 4071 + 982. Inversate: a = [1, 7, 0, 4], b = [2, 8, 9].

i = 0: 1 + 2 + 0 = 3 → cifră 3, carry 0
i = 1: 7 + 8 + 0 = 15 → cifră 5, carry 1
i = 2: 0 + 9 + 1 = 10 → cifră 0, carry 1
i = 3: 4 + 0 + 1 = 5 → cifră 5, carry 0

Rezultat inversat: [3, 5, 0, 5]. Citit normal, de la indexul mare la mic: 5053. Verificare: 4071 + 982 = 5053. Corect.

rez	3	5	0	5
	0	1	2	3
	unitati			mii

Rezultatul 5053 stocat inversat: cifra unităților pe indexul 0.

Implementare C++

#include <iostream>
#include <vector>
#include <string>
using namespace std;

// citeste un numar mare din string si il stocheaza inversat (unitati pe index 0)
vector<int> citeste(const string &s) {
    vector<int> nr;
    for (int i = (int)s.size() - 1; i >= 0; i--) {
        nr.push_back(s[i] - '0');   // caracter -> cifra
    }
    return nr;
}

// aduna doua numere mari stocate inversat, returneaza tot inversat
vector<int> aduna(const vector<int> &a, const vector<int> &b) {
    vector<int> rez;
    int n = max(a.size(), b.size());
    int carry = 0;
    for (int i = 0; i < n; i++) {
        int cifraA = (i < (int)a.size()) ? a[i] : 0;   // 0 daca s-a terminat
        int cifraB = (i < (int)b.size()) ? b[i] : 0;
        int suma = cifraA + cifraB + carry;
        rez.push_back(suma % 10);   // cifra de scris
        carry = suma / 10;          // transportul spre pozitia urmatoare
    }
    if (carry != 0) {
        rez.push_back(carry);       // carry-ul final devine cifra noua
    }
    return rez;
}

int main() {
    vector<int> a = citeste("4071");
    vector<int> b = citeste("982");
    vector<int> rez = aduna(a, b);

    // afisam de la cifra mare la cea mica (parcurgem invers)
    for (int i = (int)rez.size() - 1; i >= 0; i--) {
        cout << rez[i];             // 5053
    }
    cout << "\n";
    return 0;
}

Complexitate

Fie n și m lungimile celor două numere. Parcurgem o singură dată până la poziția cea mai mare, deci atingem fiecare cifră o dată.

Mărime	Valoare	De ce
Timp	O(max(n, m))	o trecere prin cifre, plus eventual carry-ul final
Spațiu	O(max(n, m))	rezultatul are cel mult `max(n, m) + 1` cifre

Observația-cheie

Rezultatul poate avea cu o cifră mai mult decât cel mai lung operand: 999 + 1 dă 1000, adică patru cifre dintr-un număr de trei. Acea cifră în plus vine exact din carry-ul rămas după ultima poziție, motiv pentru care îl adăugăm separat.

Greșeli frecvente

Uiți carry-ul final: după buclă mai poate rămâne carry = 1 (ex. 999 + 1). Dacă nu adaugi if (carry != 0), pierzi cifra cea mai semnificativă.
Nu tratezi lungimi diferite: dacă mergi doar până la a.size(), ignori cifrele rămase din b. Mergi până la max(n, m) și ia 0 pentru cifra lipsă.
Aduni de la cifra mare: dacă pornești de la cea mai semnificativă cifră, transportul ar trebui să curgă înapoi — exact de ce stocăm inversat și pornim de la unități.
Confuzi % 10 cu / 10: cifra scrisă e suma % 10, iar transportul e suma / 10. Inversate, ai cifre peste 9 sau carry mereu zero.

Vizualizare

Urmărește cum se aliniază cele două numere la unități și cum apare „1”-ul de transport care urcă spre coloana următoare, exact ca pe hârtie.

Indiciu

Folosește săgețile ← și → ca să avansezi poziție cu poziție. La fiecare pas, uită-te la cifra scrisă (suma % 10) și la transportul dus mai departe (suma / 10).

Recapitulare

Aduni cifră cu cifră de la unități (index 0): suma = a[i] + b[i] + carry, scrii suma % 10, duci suma / 10.
Tratezi lungimi diferite considerând 0 pentru cifra care lipsește și mergi până la max(n, m).
După bucle, dacă a rămas transport, îl adaugi ca o cifră nouă — altfel pierzi cifra cea mai mare.