Grade 9 · Frequency arrays, prefix sums and the Sieve of EratosthenesCitește în română
Common digits of two numbers
Original: Cifrele comune a două numere
O(n)C++1754 lines2 examples
The idea
In two arrays of 10 positions we mark which digits appear in each number (aparA[c], aparB[c]). The common digits are the ones marked in both arrays; we print them in increasing order, or NO if there are none.
Original description (Romanian)
Marcăm în doi vectori de 10 poziții ce cifre apar în fiecare număr (aparA[c], aparB[c]). Cifrele comune sunt cele marcate în ambii vectori; le afișăm crescător sau NU dacă nu există.
- Complexity
- O(ka + kb), where ka, kb are the numbers of digits
- Grade
- Grade 9 (Clasa a IX-a)
Examples
Example 1
Input
72413 3017
Expected output
1 3 7
Example 2
Input
222 135
Expected output
NU
The code
Comments are in Romanian, as in the original collection. Edit freely: you can reset at any time.
/*
* Titlu: Cifrele comune a două numere
* Clasa: 9
* Capitol: Frecvență, sume parțiale și ciurul lui Eratostene
* Descriere: Marcăm în doi vectori de 10 poziții ce cifre apar în fiecare
* număr (aparA[c], aparB[c]). Cifrele comune sunt cele marcate în
* ambii vectori; le afișăm crescător sau NU dacă nu există.
* Complexitate: O(ka + kb), unde ka, kb sunt numerele de cifre
*
* Exemplu
* Intrare: 72413 3017
* Ieșire: 1 3 7
*
* Exemplu
* Intrare: 222 135
* Ieșire: NU
*/
#include <iostream>
using namespace std;
int main()
{
long long a, b;
bool aparA[10] = {false}, aparB[10] = {false};
cin >> a >> b;
do
{
aparA[a % 10] = true;
a = a / 10;
}
while (a > 0);
do
{
aparB[b % 10] = true;
b = b / 10;
}
while (b > 0);
bool exista = false;
for (int c = 0; c <= 9; c++)
{
if (aparA[c] && aparB[c])
{
cout << c << ' ';
exista = true;
}
}
if (!exista)
{
cout << "NU";
}
cout << '\n';
return 0;
}
Runs on a real g++ (C++17, -O2) through Compiler Explorer. Keep runs short; there's a time limit.