else return -1;
}
==

Putem aborda probabilistic. Astfel dacă alegem un număr aleator şi există o celebritate, avem probabilitatea 0.5 să nu îl nimerim, dacă alegem k numere aleatoare din şirul respectiv, atunci avem probabilitatea
(˝)^k să nu îl nimerim. Astfel algoritmul nostru va fi să luăm k numere aleatoare, iar apoi să numărăm de câte ori apare fiecare din aceste k numere în şirul nostru. Dacă folosim o structură ce mapează chei valori atunci algoritmul va avea complexitate O(n + k) şi probabilitate de reuşită P = 1 - (˝)^k. În practică o valoare de 10 pentru k ne dă o probabilitate de reuşită de 0.999. Să vedem mai departe codul:
== code(cpp) |

    return -1;
}
==

Un ultim algoritm şi cel mai eficient dintre cele prezentate apare în lucrarea [1] şi probabil acesta este cunoscut cititorilor. Autorii au un mod plastic de a prezenta algoritmul:
Imaginaţi-vă o sală de conferinţă în care votanţii ţin fiecare o placă ce poartă numele candidatului preferat. Să presupunem se ajunge la o bataie generală în care votanţii cu convingeri diferite încep să se lovească reciproc cu plăcile. Să mai presupunem că fiecare votant care pune la pământ un membru cu alte convingeri este simultan şi el pus la pământ de adversar. Este evident că dacă ar fi vreun candidat care are mai multe voturi decăt toate voturile celorlalţi candidaţi, atunci această luptă va fi câştigată de acest candidat şi la dispariţia haosului din urma luptei, votanţii ce au rămas în picioare vor fi susţinători ai candidatului amintit. În caz că nu există o majoritate clară pentru un candidat sau altul, la finalul luptei rămân ăn picioare votanţi care susţin acelaşi candidat, dar acesta poate să nu fie reprezentantul majorităţii. Deci, în general, dacă cineva rămâne în picioare, preşedintele conferinţei este obligat să verifice dacă întradevar candidatul întruneşte votul a jumătate plus unu de votanţi. Algoritmul practic folosit de noi va fi un fel de joc al împerecherilor între candidaţi de opinii diferite până când toţi votanţii rămaşi necuplaţi vor susţine acelaşi candidat.
Realizăm acest algoritm parcurgând lista votanţilor şi ţinând un contor cu numărul de candidaţi k neîmperecheaţi până la pasul curent, evident dacă ei sunt neîmperecheaţi trebuie să susţină acelaşi candidat cand pentru că altfel am fi putut să cuplăm câţiva dintre ei.

    else return – 1;
}
==

Această problemă a fost propusă în prima rundă a concursului Bursele Agora în 2005, Atunci nu era posibilă ţinerea tuturor numerelor din fişier în memorie şi citirea numerelor era greoaie.Doar doi concurenţi au reuşit obţinerea unui punctaj maxim la acea rundă. Autorul a fost unul dintre aceştia, el a evitat citirea de două ori a fişierului de intrare prin folosirea soluţiei cu cifre, în care calcula două rezultate pentru două baze diferite b1 şi b2 alese aleator la startul rulării, iar apoi  verifica dacă candidaţii care erau probabil câştigatori erau egali. Aceasta rezolvare făcea improbabilă scrierea unui răspuns incorect.
Vom generaliza acum problema: Se dă un şir de n numere naturale şi un număr întreg k, se cere determinarea tuturor elementelor care apar de cel puţin [n/k]+1 ori în şir.

Evident dacă un număr apare de cel puţin [n/k] + 1 ori în şir atunci el va apărea în şirul sortat pe una din poziţiile i * [n/k] cu i de la 1 la k. De aici se conturează algoritmul următor: determinăm în O(n * k) elementele de pe poziţiile i * [n/k] iar apoi verificăm care dintre acestea sunt elemente majoritare în sensul menţionat mai sus. Acest algoritm are complexitate liniară daca îl considerăm pe k o constantă.
A doua soluţie este similară cu cea mai bună soluţie pentru prima problemă, numai că în loc să grupăm câte doi votanţi diferiţi vom grupa câte k votanţi cu păreri diferite.

== code(cpp) |
int[] mooreKMajority(int n, int[]  a, int k) {
    int[] cand = new int[k - 1], notMatched = new int[k - 1],  num = new int[k-1];