Numărarea aparițiilor unei cifre în C++

De câte ori apare cifra 0 în 10020? Răspunsul este 3. Problema pare o simplă repetare, dar intrarea n = 0 schimbă alegerea buclei: reprezentarea zecimală a lui zero are o cifră, chiar dacă nu putem intra într-un while (n > 0).

Cerință și limite

Citim numărul natural n, între 0 și 10^18 inclusiv, și cifra c, între 0 și 9. Afișăm câte cifre egale cu c există în scrierea zecimală obișnuită a lui n, fără zerouri adăugate în față. Folosim long long pentru număr și int pentru contor: cel mult 19 cifre sunt examinate.

Pentru 10020, cifrele examinate sunt 0, 2, 0, 0, 1, iar contorul ajunge la 3.Mărește schema ↗

Urmărirea pașilor

Operația n % 10 extrage cifra din dreapta. Operația n /= 10 elimină acea cifră. Pentru 10020 și c = 0, examinăm succesiv 0, 2, 0, 0, 1. Contorul devine 1, 1, 2, 3, 3. Ordinea inversă de examinare nu schimbă numărul aparițiilor.

Înaintea fiecărui pas, contorul păstrează exact aparițiile din cifrele deja eliminate. Dacă cifra nouă este cea căutată, îl mărim o dată. Când nu mai rămâne nimic de eliminat, contorul reprezintă întregul număr.

Program complet

Bucla do while execută primul pas și pentru n = 0. Nu avem nevoie de un caz separat și nici de conversie în text.

#include <iostream>
using namespace std;
int main() {
    long long n; int c;
    cin >> n >> c;
    int aparitii = 0;
    do {
        if (n % 10 == c) ++aparitii;
        n /= 10;
    } while (n != 0);
    cout << aparitii << '\n';
}

Ce verifici înainte să trimiți

Pentru 0 0, rezultatul este 1. Pentru 0 7, este 0. Pentru 777 7, este 3. Pentru 10020 0, este 3. Un test cu o cifră absentă verifică dacă ai inițializat contorul cu zero, nu cu unu.

Programul consumă valoarea lui n. Dacă cerința mai folosește numărul inițial, lucrează pe o copie. Nu acceptăm numere negative în această problemă; semnul nu este o cifră. Nici 0012 nu este un număr cu patru cifre în modelul numeric ales. Pentru coduri care păstrează zerouri inițiale trebuie citit text.

Timpul este O(d), unde d este numărul de cifre, iar memoria suplimentară este O(1). Spus în funcție de valoarea pozitivă a numărului, timpul este O(log n); cazul zero se rezolvă într-un pas.

Exersează

1. Pentru 505050 și cifra 5, calculează răspunsul înainte să rulezi. Răspuns: 3.
2. Modifică doar condiția pentru a număra cifrele pare. Pentru 1024 obții 3, deoarece și zero este par.
3. Explică de ce o buclă cu test inițial dă un răspuns greșit pentru 0 0, deși trece testul 10020 0.

Continuă cu extragerea cifrelor și inversul unui număr, apoi compară formele de buclă și reprezentarea în alte baze.

Întrebări frecvente

Cum număr aparițiile unei cifre într-un număr în C++?

Compară pe rând ultima cifră, obținută cu n % 10, cu cifra căutată, apoi elimin-o prin n /= 10. Mărește contorul numai la egalitate. Pentru 10020, cifra 0 apare de trei ori.

De câte ori apare cifra zero în numărul 0?

O singură dată: scrierea zecimală a numărului 0 conține o cifră. O buclă do while prelucrează această cifră; un while (n > 0) ar sări peste ea.

Se numără și zerourile de la începutul unui număr?

Nu în reprezentarea numerică obișnuită: 0012 și 12 reprezintă aceeași valoare. Dacă zerourile inițiale contează, de exemplu într-un cod, citește și prelucrează intrarea ca text.