bayre moore algo

First, we claim: given n numbers and the k counters, only less than n/(k+1) times pair-out can happen.
That is to say:

given n numbers and 1 counter (which is the majority element problem), at most (n/2) times pair-out can happen, which will lead to the survival of the only element that appeared more than n/2 times.
given n numbers and 2 counters (which is our case), at most n/3 times of pair-out can happen, which will lead to the survival of elements that appeared more than n/3 times.
given n numbers and k counters, at most (n/k+1) times of pair-out can happen, which will lead to the survival of elements that appeared more than n/(k+1) times.
If this is the case, then n elements using two counters can at most pair out less than (n/3) times, which will result in the survival of the elements that appears more than (n/3) times.