Cum putem rezolva problema asta?

O solutie naiva, dar eficienta ar fi sa luam cateva nume votate aleatoare din sir si sa verificam pentru fiecare nume daca este sau nu al castigatorului alegerilor. Cand alegem un nume aleator avem probabilitatea p > 1/3 ca am ales numele viitorului castigator. Deci daca alegem k valori vom avea un timp de executie de ordinul O(kn) si probabilitatea de a gasi peresedintele mai mare de 1 - (1/3)^k.

O solutie naiva, dar eficienta ar fi sa luam cateva nume votate aleatoare din sir. Cum castigatorul apare ca optiunea a multi votanti, daca alegem destul de multe valori din sirul optiunilor vom da cu probabilitate mare peste castigator. Cand alegem un nume aleator avem probabilitatea p > 1/3 ca am ales numele viitorului castigator. Deci daca alegem k valori vom avea un timp de executie de ordinul O(kn) pentru a verifica daca una dintre cele k valori e cea buna si probabilitatea de a gasi peresedintele mai mare de 1 - (1/3)^k.

Alta idee vine de la faptul ca in sirul sortat, elementele de valori egale vor fi pe pozitii consecutive. Astfel numele presedintelui va aparea pe cel putin n/3 + 1 pozitii consecutive. Deci numele presedintelui va aparea sigur pe cel putin una din pozitiile n/3 sau 2n/3 din sir. Astfel putem folosi un algoritm de selectie pentru a gasi in O(n) elementele de pe pozitiile n/3 si 2n/3 si apoi in O(n) putem verifica care dintre acesti doi candidati au castigat.