Question

Fișierul “bac.txt” conține un șir de cel mult 10^6 numere naturale din intervalul [0,10^3), separate prin câte un spațiu. se cere să se afișeze pe ecran cea mai mare cifră dintre cele care sunt comune tuturor termenilor șirului aflat în fișier, sau mesajul ,,nu există” dacă nu există nicio astfel de cifră. Proiectați un algoritm eficient din punct de vedere al timpului de executare.
Exemplu: dacă fișierul conține numerele
701 917 17 171 817 771 71
atunci se afișează pe ecran se afișează 7 (cifrele 1 și 7 sunt comune tuturor termenilor șirului)

Answer 1

#include <fstream>// ifstream

#include <iostream>// cout

#include <cstring>// memset()

using namespace std;

char candidat_valid[10];

char frecv_cif[10];

int main(){

memset(candidat_valid, 1, 10);// consideram toate cifrele "candidati" de la inceput si vedem care e cel mai mare care a ramas la sfarsit

int x, i;

ifstream fin("bac.txt");

while(fin >> x){

 memset(frecv_cif, 0, 10);

 while(x){

  frecv_cif[x%10]++;// construim vectorul de frecventa cu numarul de cifre

  x/=10;

 }

 for(i = 0; i < 10; i++){

  if(frecv_cif[i] == 0)// daca o cifra nu apare deloc

   candidat_valid[i] = 0;// nu mai este comuna pentru toate numerele

 }

}

for(i = 9; i >= 0; i--){

 if(candidat_valid[i]) // afisam cea mai mare cifra care a ramas

 {

  cout << i;

  break;

 }

}

if(i == -1)cout << "nu exista";// sau mesajul "nu exista" daca nu exista o cifra comuna intre toate numerele

}