Scăderea numerelor mari — cu împrumut

De ce contează?

Îți amintești scăderea pe hârtie din clasele mici? Când cifra de sus era prea mică, „împrumutai” o zece de la vecinul din stânga: tăiai cifra lui, o micșorai cu 1 și adăugai 10 la cifra ta. Calculatorul face exact același truc, doar că „vecinul” este poziția următoare din vector.

Ideea: scădem ca pe hârtie, cu împrumut

Reamintim convenția capitolului: un număr mare este un vector<int> în care cifra unităților stă pe indexul 0 (numărul e ținut inversat, little-endian), iar baza este 10. Pe indexul i se află cifra care valorează 10^i.

Pentru scădere presupunem că a >= b, deci rezultatul este nenegativ. Mergem poziție cu poziție, de la unități (index 0) spre cifrele mari, și scădem cifra lui b din cifra lui a. Dacă cifra de sus e prea mică, împrumutăm 10 de la poziția următoare (index i + 1) și ținem minte un „borrow” pe care îl scădem din pasul următor. Exact ca pe hârtie.

Exemplu pas cu pas: 4002 - 137

Inversate, cele două numere arată așa:

a = 4002 → [2, 0, 0, 4]
b = 137 → [7, 3, 1]

Parcurgem de la index 0, cu borrow pornit de la 0:

i = 0: 2 - 7 - 0. E negativ → împrumut: 2 + 10 - 7 = 5, borrow = 1. Rezultat: 5
i = 1: 0 - 3 - 1. E negativ → împrumut: 0 + 10 - 3 - 1 = 6, borrow = 1. Rezultat: 6
i = 2: 0 - 1 - 1. E negativ → împrumut: 0 + 10 - 1 - 1 = 8, borrow = 1. Rezultat: 8
i = 3: 4 - 0 - 1 = 3. E pozitiv → borrow = 0. Rezultat: 3

Vectorul rezultat (inversat) este [5, 6, 8, 3], adică numărul 3865. Vezi cum împrumutul s-a propagat în lanț prin zerourile lui 4002.

Implementare C++

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

// scade b din a, presupunand a >= b; numere inversate (unitatile pe index 0)
vector<int> scade(const vector<int>& a, const vector<int>& b) {
    vector<int> r;
    int borrow = 0;
    for (int i = 0; i < (int)a.size(); i++) {
        int cifra = a[i] - borrow;          // scadem si imprumutul anterior
        if (i < (int)b.size()) {
            cifra -= b[i];                  // doar daca b mai are cifre aici
        }
        if (cifra < 0) {
            cifra += 10;                    // imprumutam 10 de la pozitia urmatoare
            borrow = 1;
        } else {
            borrow = 0;
        }
        r.push_back(cifra);
    }
    // eliminam zerourile nesemnificative din capatul cu index mare
    while (r.size() > 1 && r.back() == 0) {
        r.pop_back();
    }
    return r;
}

int main() {
    vector<int> a = {2, 0, 0, 4};   // 4002 inversat
    vector<int> b = {7, 3, 1};      // 137 inversat

    vector<int> r = scade(a, b);

    // afisam de la cifra cea mai semnificativa (index mare) spre unitati
    for (int i = (int)r.size() - 1; i >= 0; i--) {
        cout << r[i];               // 3865
    }
    cout << "\n";
    return 0;
}

Bucla merge până la lungimea lui a (cel mai lung, fiindcă a >= b). Când b nu mai are cifre pe poziția curentă, scădem doar borrow. La final tăiem zerourile din capătul semnificativ și afișăm vectorul invers.

Complexitate

Fie n numărul de cifre al lui a (cel mai mare operand).

Operație	Timp	De ce
scăderea cifră cu cifră	O(n)	o singură trecere prin vector
eliminarea zerourilor	O(n)	în cel mai rău caz tai aproape toate cifrele
total	O(n)	proporțional cu numărul de cifre

Observația-cheie

Eliminarea zerourilor nesemnificative se face DOAR la final, dintr-un singur capăt: cel cu index mare (cifrele cele mai semnificative). Păstrăm condiția r.size() > 1 ca să nu golim vectorul de tot — dacă rezultatul este chiar 0, trebuie să rămână un singur element, cifra 0, altfel nu mai ai ce afișa.

Greșeli frecvente

Uiți să elimini zerourile din față: 4000 - 3999 = 1, dar fără tăiere vectorul rămâne [1, 0, 0, 0] și afișezi „0001”. Taie zerourile din capătul cu index mare la final.
Greșești direcția împrumutului: împrumuți de la poziția mai mare (index i + 1), nu de la cea mai mică. Concret, aduni 10 la cifra curentă și pui borrow = 1 pentru pasul URMĂTOR.
Nu verifici că a >= b: dacă a < b, rezultatul e negativ și borrow rămâne 1 după ultima poziție — ai nevoie de semn (vezi mai jos). Algoritmul de aici presupune a >= b.
Index out of range pe poziția următoare: nu citi b[i] fără să verifici i < b.size(); b e de obicei mai scurt decât a. Aici scădem b[i] doar în interiorul verificării.

Rezultatul 3865 ca vector inversat, înainte de afișare:

r	5	6	8	3
	0	1	2	3

Rezultatul 4002 − 137 = 3865, ținut inversat: unitatea (5) pe indexul 0, cifra cea mai semnificativă (3) pe indexul 3.

Dacă a < b, diferența este negativă. Atunci se reține semnul separat: compari întâi numerele, scazi mereu pe cel mic din cel mare și pui semnul „−” în față. Acest caz iese din scopul lecției de aici.

Recapitulare

Scazi cifră cu cifră de la index 0 spre cifrele mari; când cifra de sus e prea mică, împrumuți 10 de la poziția i + 1 și ții un borrow pentru pasul următor.
La final elimini zerourile nesemnificative din capătul cu index mare, dar păstrezi cel puțin o cifră (pentru rezultatul 0).
Algoritmul presupune a >= b (rezultat nenegativ); pentru a < b ai nevoie de un semn ținut separat.