How to prove that algorithm returns the value which appears more than $n/2$ times in the array?

Question

Given the following algorithm (pseudocode):

alg1(A[1,..,n])
    i <- 1
    candidate <- NULL
    count <- 0
    while(i <= n)
        if(count = 0)
            candidate <- A[i]
            count <- count + 1
        else if(candidate = A[i])
            count <- count + 1
        else
            count <- count - 1
        i <- i + 1
    return candidate

I need to prove that if a value appears more than $n \over 2$ times (let the value be named $M$) in the array then it will be returned.

$\mathbf{EDIT:}$ here's my 2 attempt. First we assume that the array $A$ contains at least 3 elements (if less then the proof is trivial). The element which appears more than $n/2$ times is $M$ else it's $M'$. Let a two-element combination of $MM'$ or $M'M$ be called $C$. Every time we traverse a $C$ the count decreases by one.

CASE 1: If the pattern is strictly alternating combinations of type $C$ then the first and the last element must be $M$ (otherwise $M$ will not appear more than $n/2$ times) and this means that after the last iteration the candidate is $M$.

CASE 2: We can see that after any number of adjacent $C$'s the counter will be $0$ and the candidate will be either $M$ or $M'$. It is given that more than $n/2$ elements of $M$ do exist in the array, so the number of $C$ combinations must be supplemented by at least $1$ occurrence of $k$ adjacent elements of $M$ either before $C$'s or after $C$'s. If it's after, then the next candidate is $M$ and it will continue to be so as long as we keep traversing $k$ elements of adjacent $M$'s. If it's before than the count will be at least $1$ before it proceeds to iterate through $C$'s and essentially it'll behave just like CASE 1.

I'm still aware that the proof is not perfect but I feel like it's an improvement. Suggestions/advice is very welcome.

Answer 1

Let us prove the following claim by induction:

Suppose that the first $i$ symbols contain $j$ copies of $\sigma$, and let $\delta = j-(i-j) = 2j-i$. After the $i$th iteration of the loop:

(a) If $\delta > 0$ then $candidate=\sigma$ and $count \geq \delta$.

(b) If $\delta \leq 0$ then either $candidate=\sigma$ or $count \leq -\delta$.

This certainly holds for $i = 0$. Given that it holds for $i$, we now show it holds for $i':=i+1$ as well. Let $j,j'$ be the number of copies of $\delta$ in the first $i,i'$ symbols (respectively), and let $\delta=2j-i$, $\delta'=2j'-i'$. Define $candidate,candidate'$ and $count,count'$ as the values of these variables after $i,i'$ iterations (respectively). There are several cases to consider.

Case 1: the $i'$th symbol is $\sigma$.

Case 1a: $\delta > 0$. The induction hypothesis states that $candidate = \sigma$ and $count \geq \delta$. Therefore $candidate' = \sigma$ and $count' = count+1 \geq \delta+1 = \delta'$.

Case 1b: $\delta = 0$, $candidate = \sigma$. This is the same as Case 1a.

Case 1c: $\delta = 0$ and $candidate \neq \sigma$. The induction hypothesis states that $count = 0$. Therefore $candidate' = \sigma$ and $count' = 1 = \delta'$.

Case 1d: $\delta < 0$ and $candidate = \sigma$. This is the same as Case 1a.

Case 1e: $\delta < 0$ and $candidate \neq \sigma$. The induction hypotehsis states that $count \leq -\delta$. Therefore either $candidate' = \sigma$, or $count' = count-1 \leq -(\delta+1) = -\delta'$.

Case 2: the $i'$th symbol is $\tau \neq \sigma$.

Case 2a: $\delta > 0$. The induction hypothesis states that $candidate = \sigma$ and $count \geq \delta$. Therefore $candidate' = \sigma$ and $count' = count-1 \geq \delta-1 = \delta'$.

Case 2b: $\delta = 0$ and $candidate = \sigma$. If $count = 0$ then $count' = 1 = -\delta'$. Otherwise, $candidate' = \sigma$.

Case 2c: $\delta = 0$ and $candidate \neq \sigma$. The induction hypothesis states that $count = 0$, and so $count' = 1 = -\delta'$.

Case 2d: $\delta < 0$ and $candidate = \sigma$. This is the same as Case 2b (with $1 \leq -\delta'$ in the first case).

Case 2e: $\delta < 0$ and $candidate \neq \sigma$. If $candidate = \tau$ then $count' = count + 1 \leq -(\delta-1) = -\delta'$. If $candidate \neq \tau$ then $count' = 1 \leq -\delta'$.

---

Given the claim, we see that if $\sigma$ appears more than $n/2$ times, then when $i=n$ we have $\delta > 2(n/2)-n > 0$, and so $candidate = \sigma$.

Answer 2

Note: In my opinion, although the answer given by @Sunny Wang is slightly hard to follow, it is in the right direction. Maybe the author would like to come back and improve his/her answer. Therefore, I will only give some high-level hints here.

Playing with some examples, you will find that the program amounts to keeping eliminating (by decreasing the counter, of course) a pair of distinct elements. Therefore, if a value appears more than $\frac{n}{2}$ times, it (and only it; this is also important) survives and will be returned.

Answer 3

I'd like to try to use contradiction to prove your algorithm.

The algorithm can be described with a stack model. The procedure is equal to the operation of pushing and popping elements while scanning an array. As for each element scanned, if the stack is empty or the element is equal to the element at the top of the stack, push it; or pop an element. Since we initialize the stack with the array's first element and we push one element as soon as the stack is empty, our popping one element operation in each loop will remain the stack operations legal.

For the elements in the stack meantime are equal, the value which appears more than $\frac{n}{2}$ times must be returned. We can prove it by contradiction. Assume the value is not returned, any element of this value will lead to another element of a different value be popped. But it is impossible. We do not have so many elements. So the assumption is not correct. In this way, we prove that the algorithm is correct.

Answer 4

Proof by induction:

If $n=1$, the algorithm returns A[1], which is correct.

if $n>1$, and $M$ appears $t$ times in A, then either:

• it appears $t$ times in A[1],...,A[n-1] and A[n]!=M, in which case the nth iteration of the while loop takes candidate=M and count$=t-(n-1-t)=2t-n+1$, but $t>n/2$ implies $2t-n+1>0$ therefore count>0 and alg1 returns $M$.
• it appears $t-1$ times in A[1],...,A[n-1] and A[n]=M, in which case, in the nth iteration of the while loop, either candidate=M and alg1 returns M, or candidate!=M and count=0 and alg1 returns A[n] which is $M$.