De ce contează?
Triezi cutii după greutate și vrei s-o găsești pe cea mai grea. Nu le cântărești pe toate deodată — compari câte una cu „campionul" curent. Dacă găsești una mai grea, ea devine noul campion. Exact asta faci și cu cifrele unui număr: menții un câștigător și îl actualizezi pe parcurs.
Ideea de maxim și minim curent
Menținem un maxim curent și îl actualizăm la fiecare cifră extrasă. Urmărește pentru n = 3927:
Pornim: maxim = -1
Cifra 7: max(-1, 7) = 7 → maxim = 7
Cifra 2: max(7, 2) = 7 → maxim = 7
Cifra 9: max(7, 9) = 9 → maxim = 9
Cifra 3: max(9, 3) = 9 → maxim = 9
Rezultat: 9(Cifrele sunt extrase de la dreapta la stânga, dar ordinea nu afectează maximul.)
Inițializează maxim = -1 și minim = 10. Valorile sunt în afara intervalului [0, 9], deci orice cifră reală va actualiza corect variabila la prima comparație. Dacă inițializezi minim = 0, nu vei detecta că minimul este 0 atunci când numărul conține cifra 0.
Implementare C++
#include <iostream>
using namespace std;
int main() {
int n;
cin >> n;
if (n == 0) {
cout << "Max: 0, Min: 0" << endl;
return 0;
}
int maxim = -1, minim = 10;
int temp = n;
while (temp > 0) {
int cifra = temp % 10;
if (cifra > maxim) maxim = cifra;
if (cifra < minim) minim = cifra;
temp /= 10;
}
cout << "Max: " << maxim << ", Min: " << minim << endl;
return 0;
}Exemplu: Input 3927 → Max: 9, Min: 2
Complexitate
| Caz | Timp | Spațiu |
|---|---|---|
| Număr cu d cifre | O(log n) | O(1) |
Greșeala 1: Inițializezi maxim = 0. Dacă toate cifrele sunt 0 (cazul n = 0), maxim rămâne 0 — aparent corect, dar nu ai parcurs nicio cifră. Inițializarea cu -1 e mai sigură și mai explicită.
Greșeala 2: Inițializezi minim = 0. Pentru numărul 123, minim rămâne 0 deși 1 e cea mai mică cifră — pentru că 0 < 1 și condiția cifra < minim nu se declanșează niciodată. Inițializează minim = 10 (mai mare decât orice cifră posibilă).
Greșeala 3: Compari cu temp (valoarea în continuă schimbare) în loc de cifra = temp % 10. Extrage cifra mai întâi, compară cu ea.