Soluţii corecte: ZoltanSzabo, Aurel Ionescu, Dan Florescu.

Cea de complexitate minimă este dată de ZoltanSzabo:

 Se știe că numărul majoritar apare de mai multe ori decât toate celelalte numere laolaltă. Deci e un algoritm eficient să creștem contorul cu 1 atunci când avem două nume identice și să scădem contorul cu 1 atunci când am citit două nume distincte.

De fiecare dată memorăm numele despre care contorul spune în acel moment că apare de mai multe ori decât alte nume.

Dacă la un moment dat contorul se anulează, înseamnă că am reușit să creem din toate datele citite perechi formate din câte două nume distincte.

În cazul cel mai nefavorabil fiecare preche conține un nume  majoritar combinat cu un alt nume. Astfel în mulțimea numelor necitite, numele majoritar își va păstra statutul în continuare, și algoritmul se poate continua până la ultimul nume citit.

Într-un caz mai favorabil există și perechi de nume în care ambele sunt nemajritare. Astfel în mulțimea numelor necitite, numele majoritar va deveni „și mai majoritar”, adică algoritmul se oate continua în acest fel până la ultimul nume citit.

Dacă s-a terminat citirea numelor putem fi siguri că numele rămas în „memoria scurtă” este chiar numele majoritar pentru care nu am reușit să găsim o pereche diferită.

           Algoritmul problemei:

Citește Nume

Anterior=Nume

Contor=1

Câttimp secvența nu s-a terminat

      Citește Nume

      Dacă Nume = Anterior

              Contor=Contor+1

       Altfel

               Contor=Contor – 1

      Sf dacă

      Dacă Contor = 0 atunci             //   avem garantia ca exista inca in nume in secventa

              Citeste Nume

              Anterior = Nume

              Contor=1

     Sf daca

Sf câttimp

Scrie Anterior                  //  ultima valoare din memoria scurta e numele majoritar

 

Notă: Problema a mai aparut şi în alte două locuri (din cautarile mele):

- M. J. Fischer and S. L. Salzberg, Finding a majority among n votes, J. of Algorithms 3:4 (Nov 1989) 362-380.

- P. Winkler, Mathematical Puzzles, A Connoisseur's Collection, (A K Peters), p. 104.