De ce contează?
Într-o sală plină, fiecare susținător al echipei tale dă mâna cu exact un adversar și amândoi ies afară — unu pentru, unu contra, se anulează. Dacă echipa ta are mai mult de jumătate din sală, oricâți adversari ar fi, după ce toate perechile au plecat tot rămâne măcar un om de-al tău în picioare. Pe acel ultim om în picioare îl găsește algoritmul.
Intuiția
Un element majoritar apare de mai mult de jumătate din ori într-un șir de
n numere (strict peste n/2). Imaginează-ți că fiecare apariție a lui e un
vot „pentru” și fiecare alt număr e un vot „contra”. Dacă pui un susținător față
în față cu un adversar, ei se anulează. Pentru că majoritarul are strict mai
multe voturi decât toate celelalte la un loc, nu poate fi anulat complet:
supraviețuiește mereu cel puțin un vot de-al lui.