**Majority Element**

Majority
element: the element that appears strictly more than n/2 times in the array.

An
Θ(n)-time algorithm to find the majority element
or reports that no such element exists:

__Hint:__ Find a candidate solution, then
determine whether this candidate is indeed the majority element.

**FIND-MAJORITY-ELEMENT(A)**

1
for i ← 1 to length[A]

2
if stack is empty

3
then push A[i]
on the stack

4
else if A[i] equals top element on the stack

5 then push A[i] on
the stack

6
else pop the stack

7
if stack is empty

8
then return NoMajority

9
candidate ← top element on the stack

10
counter ← 0

11
for i ← 1 to length[A]

12
if A[i] equals
candidate

13
then counter ← counter + 1

14
if counter > length[A]/2

15
then return candidate

16
return NoMajority

__Claim:__ If a majority element exists, it will be on the stack
at the end of this part of the procedure.

__Proof:__ (by contradiction)

Call
the majority element x, appears i > n/2 times.

Each
time x is encountered, it is either pushed on the stack or an element
(different from x) is popped off the stack.

There
are n − i < i elements different from x.

*Assume x is not on the stack at the end
of the procedure.*

Then,
each of the i elements of x must have either popped
another element off the stack, or been popped off by another element. However,
there are only n − i < i other elements, so this is a contradiction.

**Therefore, x must be on the stack at the
end of the procedure.**

Running
time: Θ(n).

(from carlstrom.com/stanford/cs161/ps1sol.pdf)

**Problem 1510 – Timus – Order:**

http://acm.timus.ru/problem.aspx?space=1&num=1510

program _1510;

const nmax=500000;

var s: array[0..nmax] of
longint;

i, a, n: longint;

begin

readln(n);

s[0]:=0;

for i:=1 to n do

begin

readln(a);

if s[0]=0 then begin s[0]:=1; s[1]:=a; end

else if a=s[s[0]] then begin inc(s[0]); s[s[0]]:=a; end

else if i<>n then dec(s[0]); {when x appears exactly
n/2 times}

end;

writeln(s[s[0]]);

end.