Grade 12 · Big numbersCitește în română
Comparing two big numbers
Original: Compararea a două numere mari
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)
- Chapter
- Big numbers
Examples
Input
123456789012345678901 99999999999999999999
Expected output
>
Input
1234 1243
Expected output
<
Input
0050 50
Expected output
=
The code
Comments are in Romanian, as in the original collection. Edit freely: you can reset at any time.
/*
* 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.