# Major element

Let's define major element as element such that occurs in an array > n / 2 times

To find it, we'll additionally store two variables: cadidate and count

Let's go through the array: if count = 0 then we'll pick current element as a candidate

If current element equals to candidate, we'll increase count by 1 and else decrease by 1

So if we are guaranteed that input array contains major element, then it will be certainly found

Thus, we have algorithm T(n), that uses O(1) additional space

Else, just do a simple check for candidate

Proof of correctness of that algorithm may be found here