You are given an array A$[1..$n$]$ of n integers. We define an element x to be $$in the majority$$

if the set Ix $=\{$i : A$[$i$]=$ x$\}$ has size strictly more than n$/2.$ Note that any array A can have

at most one element in the majority.

Given an array A$[1..$n$],$ design an O$($n$)$ time algorithm with the following guarantee:

$$ If there is an element x which is in the majority, then it outputs x;

$$ else it outputs $$None$.$

You may assume that any two elements in the array can be compared in O$(1)$ time.

Hint: Suppose n is even. Pair the elements in the array in groups of $2.$ For each pair, if

both elements are distinct, remove both elements from the array. If they are the same, retain

exactly one of them in the array and discard the other. Prove that this step $($i$)$ shrinks the

array size by at least $1/2$; $($ii$)$ the majority element $($if any$)$ continues to be the majority

element in the reduced array as well. Also, pay special attention on how to handle the case

when n is odd.