Vectorul caracteristic

Unele probleme nu ne cer să reținem valori, ci doar să știm dacă anumite valori apar sau nu. Pentru astfel de situații folosim un vector special, numit vector caracteristic.

Practic, „traducem” o valoare într-o poziție: dacă valoarea x apare, punem 1 pe poziția x a vectorului caracteristic. Tehnica este utilă mai ales atunci când valorile pe care le urmărim sunt puține și mici, de exemplu cifrele de la 0 la 9, caz în care ne ajunge un vector cu 10 poziții.

Enunț. Se citesc n numere naturale de câte două cifre. Să se afișeze cifrele care nu apar în componența niciunui număr.

#include <iostream>
using namespace std;
int n, C[10];
int main() {
    int x;
    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> x;
        C[x % 10] = 1; // cifra unitatilor
        C[x / 10] = 1; // cifra zecilor
    }
    for (int i = 0; i <= 9; i++)
        if (C[i] == 0)
            cout << i << ' ';
    return 0;
}

> 5
> 20 33 23 54 40
1 6 7 8 9 

> 7
> 12 24 55 79 88 52 92
0 3 6

Pentru intrarea 5 și numerele 20 33 23 54 40 se afișează 1 6 7 8 9, iar pentru 7 și numerele 12 24 55 79 88 52 92 se afișează 0 3 6.

Vectorul C are câte o poziție pentru fiecare cifră, de la 0 la 9. Pentru fiecare număr citit marcăm cu 1 pozițiile corespunzătoare cifrei unităților (x % 10) și cifrei zecilor (x / 10). La final, pozițiile rămase pe 0 indică exact cifrele care nu au apărut niciodată.

Pentru că vectorul C a fost declarat global, el pornește automat cu toate pozițiile pe 0, adică „nicio cifră nu a apărut încă”, exact starea de la care vrem să pornim (vezi observația despre vectorii globali din pagina Declararea vectorilor).

Vectorul caracteristic răspunde la întrebarea „apare sau nu?”, nu la „de câte ori apare?”. Dacă o valoare apare de mai multe ori, poziția ei rămâne tot 1. Atunci când ne interesează numărul de apariții, folosim o variantă înrudită: vectorul de frecvență.

Vectorul caracteristic este o tehnică simplă și elegantă de a urmări prezența unor valori, transformând fiecare valoare într-o poziție marcată cu 0 sau 1. Este foarte des întâlnit în problemele cu cifre sau cu mulțimi de numere mici. Pasul firesc următor este vectorul de frecvență, care numără aparițiile în loc să le marcheze.