Numere mari: scăderea

Scăderea numerelor mari funcționează invers față de adunare: în loc de transport, folosim împrumut (borrow) când cifra de sus e mai mică decât cea de jos.

Presupunem că a ≥ b (altfel rezultatul e negativ - vezi secțiunea specială la final).

Algoritm

La fiecare poziție:

Dacă a[i] ≥ b[i] (după scăderea eventualului împrumut anterior): scădem direct.
Dacă a[i] < b[i]: împrumutăm 1 de la poziția următoare, adăugând 10 la cifra curentă. La pasul următor, scădem 1 din a[i+1] ca să „plătim” împrumutul.

transport (borrow) = 0
pentru i = 1 .. lenA:
    dif = a[i] - b[i] - transport
    dacă dif < 0:
        dif = dif + 10
        transport = 1
    altfel:
        transport = 0
    c[i] = dif

La final, eliminăm zerourile din față (de exemplu 1000 - 999 = 1, nu 0001).

Pas cu pas: `1234 - 457 = 777`

Reprezentare:

a = 1234 → a[0]=4, a[1]=4, a[2]=3, a[3]=2, a[4]=1
b = 457 → b[0]=3, b[1]=7, b[2]=5, b[3]=4, b[4]=0

Scădere:

i	a[i]	b[i]	transport	dif	c[i]	transport nou
1	4	7	0	-3 → 7	7	1
2	3	5	1	-3 → 7	7	1
3	2	4	1	-3 → 7	7	1
4	1	0	1	0	0	0

Rezultat brut: c[0]=4, c[1]=7, c[2]=7, c[3]=7, c[4]=0. După eliminarea zero-ului din față: c[0]=3 → 777 ✓.

Eliminarea zerourilor din față

După scădere, cifrele de top pot fi 0 (ex. 1000 - 999 = 1, nu 0001). Scădem lungimea cât timp cifra de top e 0:

while (c[0] > 1 && c[c[0]] == 0) {
    c[0] = c[0] - 1;
}

Important: păstrăm c[0] ≥ 1 - dacă c[0] devine 0, afișarea ar fi vidă. Rezultatul 0 are c[0] = 1 și c[1] = 0.

Cod

const int NMAX = 1005;
int a[NMAX], b[NMAX], c[NMAX];

// Presupune a >= b.
void scadere(int a[], int b[], int c[]) {
    int len = a[0];
    int transport = 0;
    for (int i = 1; i <= len; i++) {
        int dif = a[i] - b[i] - transport;
        if (dif < 0) {
            dif = dif + 10;
            transport = 1;
        } else {
            transport = 0;
        }
        c[i] = dif;
    }
    c[0] = len;
    // elimin zerourile din față
    while (c[0] > 1 && c[c[0]] == 0) {
        c[0] = c[0] - 1;
    }
}

Complexitate: O(lenA).

Compararea a două numere mari

Înainte să scădem, trebuie să știm care număr e mai mare. Dacă scădem b din a dar b > a, algoritmul de sus iese greșit (transport rămas la final).

// Returnează:
//  1 dacă a > b
//  0 dacă a == b
// -1 dacă a < b
int compara(int a[], int b[]) {
    if (a[0] != b[0]) {
        if (a[0] > b[0]) {
            return 1;
        } else {
            return -1;
        }
    }
    // aceeași lungime: comparăm cifrele de la stânga la dreapta
    for (int i = a[0]; i >= 1; i--) {
        if (a[i] != b[i]) {
            if (a[i] > b[i]) {
                return 1;
            } else {
                return -1;
            }
        }
    }
    return 0;
}

Atenție la zerouri din față la comparație: dacă un număr e 007 (cu zero-uri inutile stocate), comparația după lungime iese greșită. De aceea mereu eliminăm zero-urile din față după orice operație.

Exemplu complet: `a - b`

#include <fstream>
#include <cstring>
using namespace std;
ifstream fin("date.in");
ofstream fout("date.out");

const int NMAX = 1005;
int a[NMAX], b[NMAX], c[NMAX];
char s[NMAX];

void citire(int v[]) {
    fin >> s;
    int len = strlen(s);
    v[0] = len;
    for (int i = 1; i <= len; i++) {
        v[i] = s[len - i] - '0';
    }
}

void afisare(int v[]) {
    for (int i = v[0]; i >= 1; i--) {
        fout << v[i];
    }
    fout << "\n";
}

int compara(int a[], int b[]) {
    if (a[0] != b[0]) {
        if (a[0] > b[0]) {
            return 1;
        } else {
            return -1;
        }
    }
    for (int i = a[0]; i >= 1; i--) {
        if (a[i] != b[i]) {
            if (a[i] > b[i]) {
                return 1;
            } else {
                return -1;
            }
        }
    }
    return 0;
}

void scadere(int a[], int b[], int c[]) {
    int len = a[0];
    int transport = 0;
    for (int i = 1; i <= len; i++) {
        int dif = a[i] - b[i] - transport;
        if (dif < 0) {
            dif = dif + 10;
            transport = 1;
        } else {
            transport = 0;
        }
        c[i] = dif;
    }
    c[0] = len;
    while (c[0] > 1 && c[c[0]] == 0) {
        c[0] = c[0] - 1;
    }
}

int main() {
    citire(a);
    citire(b);

    int cmp = compara(a, b);
    if (cmp < 0) {
        // a < b: rezultatul e negativ
        fout << "-";
        scadere(b, a, c); // fac b - a și pun minus
    } else {
        scadere(a, b, c);
    }
    afisare(c);
    return 0;
}

Pentru a = 457, b = 1234:

compara(a, b) = -1 (a mai mic)
Afișează - apoi scadere(b, a, c) = 1234 - 457 = 777
Output: -777

Aplicație: suma alternantă

Calculează a₁ - a₂ + a₃ - a₄ + ... pentru numere mari.

Citești pe rând, alternezi scăderea și adunarea:

int rez[NMAX], temp[NMAX];
citire(rez); // a₁
for (int k = 2; k <= N; k++) {
    citire(temp);
    if (k % 2 == 0) {
        // scădem
        if (compara(rez, temp) >= 0) {
            scadere(rez, temp, rez);
        } else {
            // rezultatul devine negativ - trebuie tratat...
        }
    } else {
        adunare(rez, temp, rez);
    }
}

Atenție: dacă tracăkeziserul poate deveni negativ, trebuie să păstrezi și semnul într-o variabilă separată. Pentru probleme de olimpiadă care cer „răspunsul modulo M”, semnul se tratează diferit.

Greșeli frecvente

1. Nu elimini zero-urile din față

După 1000 - 999, c[0] rămâne 4 cu cifrele 1, 0, 0, 0. Afișare greșită: 0001. Mereu rulează bucla while (c[0] > 1 && c[c[0]] == 0).

2. Presupui greșit `a >= b`

Dacă a < b și rulezi scadere(a, b, c), ieși cu transport rămas sau cifre aberante. Mereu verifică cu compara(a, b) înainte.

3. Împrumut multiplu neratat

Dacă a = 1000 și b = 1, scăderea e:

Poziția 1: 0 - 1 = -1 → 9, transport = 1
Poziția 2: 0 - 0 - 1 = -1 → 9, transport = 1
Poziția 3: 0 - 0 - 1 = -1 → 9, transport = 1
Poziția 4: 1 - 0 - 1 = 0, transport = 0

Rezultat: 0999 → după eliminare: 999 ✓. Împrumutul se poate propaga prin multe cifre - asigură-te că transport e corect.

4. Caz special: `c[0] = 0`

Nu permite c[0] = 0. Dacă rezultatul e 0, c[0] = 1, c[1] = 0 - afișare validă: 0.

5. Negativ nu apare, dar problema presupune

Unele probleme garantează a >= b în input. Altele nu. Citește cu atenție enunțul.

Ce să reții

Scăderea = adunare inversă, cu împrumut în loc de transport.
Formula: dif = a[i] - b[i] - transport; dacă dif < 0: dif += 10, transport = 1.
Mereu elimină zero-urile din față la sfârșit.
Înainte să scazi, compară a cu b. Dacă a < b, scazi b - a și pui - în față.
Comparația se face întâi pe lungime, apoi pe cifre de la cel mai semnificativ la cel mai puțin.
Complexitate: O(lenA).