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(java) |

== code(cpp) |

int probabilisticMajority(int n, int[] a) {
    Random ran = new Random(System.currentTimeMilis());
    HashMap<Integer, Integer> map = new HashMap<Integer, Integer>();