Grade 12 · Big numbersCitește în română

Comparing two big numbers

Original: Compararea a două numere mari

O(n)C++1765 lines3 examples

The idea

Without leading zeros, the number with more digits is larger. If they have the same number of digits, we compare them from the most significant digit (the last index in the array) towards the units; the first position where they differ decides the result. The program prints one of the signs <, = or > between the first and the second number.

Original description (Romanian)

Fără zerouri nesemnificative, numărul cu mai multe cifre este mai mare. Dacă au același număr de cifre, le comparăm de la cifra cea mai semnificativă (ultimul indice din vector) spre unități; prima poziție pe care diferă decide rezultatul. Programul afișează unul dintre semnele <, = sau > între primul și al doilea număr.

Complexity
O(k), where k is the number of digits of the numbers
Grade
Grade 12 (Clasa a XII-a)

Examples

Example 1

Input

123456789012345678901 99999999999999999999

Expected output

>
Example 2

Input

1234 1243

Expected output

<
Example 3

Input

0050 50

Expected output

=

The code

Comments are in Romanian, as in the original collection. Edit freely: you can reset at any time.

compararea-a-doua-numere-mari.cpp
/*
 * Titlu: Compararea a două numere mari
 * Clasa: 12
 * Capitol: Numere mari
 * Descriere: Fără zerouri nesemnificative, numărul cu mai multe cifre este mai
 *            mare. Dacă au același număr de cifre, le comparăm de la cifra cea
 *            mai semnificativă (ultimul indice din vector) spre unități; prima
 *            poziție pe care diferă decide rezultatul. Programul afișează unul
 *            dintre semnele <, = sau > între primul și al doilea număr.
 * Complexitate: O(k), unde k este numărul de cifre al numerelor
 *
 * Exemplu
 * Intrare: 123456789012345678901 99999999999999999999
 * Ieșire: >
 *
 * Exemplu
 * Intrare: 1234 1243
 * Ieșire: <
 *
 * Exemplu
 * Intrare: 0050 50
 * Ieșire: =
 */
#include <iostream>
#include <string>
#include <vector>
using namespace std;

vector<int> citesteNumar(const string &s)
{
    vector<int> a;
    for (int i = (int)s.size() - 1; i >= 0; i--)
        a.push_back(s[i] - '0');
    while (a.size() > 1 && a.back() == 0)
        a.pop_back();
    return a;
}

// Întoarce -1 dacă a < b, 0 dacă a = b și 1 dacă a > b.
int compara(const vector<int> &a, const vector<int> &b)
{
    if (a.size() != b.size())
        return a.size() < b.size() ? -1 : 1;
    for (int i = (int)a.size() - 1; i >= 0; i--)
    {
        if (a[i] != b[i])
            return a[i] < b[i] ? -1 : 1;
    }
    return 0;
}

int main()
{
    string s1, s2;
    cin >> s1 >> s2;
    int r = compara(citesteNumar(s1), citesteNumar(s2));
    if (r < 0)
        cout << "<\n";
    else if (r == 0)
        cout << "=\n";
    else
        cout << ">\n";
    return 0;
}

Runs on a real g++ (C++17, -O2) through Compiler Explorer. Keep runs short; there's a time limit.