Majority Element

easyArrays & Hashing+10 XPTime limit 2s

An array of n integers has a majority element: a value that appears more than n / 2 times. Find it.

Input:

line 1: n
line 2: n integers

Output: the majority element.

Constraints: 1 ≤ n ≤ 10⁵, −10⁹ ≤ a[i] ≤ 10⁹. A majority element always exists.

Challenge: solve it in O(n) time and O(1) extra memory (look up the Boyer–Moore voting idea).

Sample input 1

3
3 2 3

Sample output 1

Sample input 2

7
2 2 1 1 1 2 2

Sample output 2

📖 Stuck? Learn the pattern

Read input from standard input and print the answer to standard output. Your code runs in a secure sandbox against the samples (Run) and hidden tests (Submit).

Loading editor…