# Majority Element solved by 1406

Feb. 21, 2014, 4:22 p.m. by Rosalind Team

Topics: Sorting

## Problem

An array $A[1..n]$ is said to have a majority element if more than half of its entries are the same.

Given: A positive integer $k \le 20$, a positive integer $n \le 10^4$, and $k$ arrays of size $n$ containing positive integers not exceeding $10^5$.

Return: For each array, output an element of this array occurring strictly more than $n/2$ times if such element exists, and "-1" otherwise.

## Sample Dataset

4 8
5 5 5 5 5 5 5 5
8 7 7 7 1 7 3 7
7 1 6 5 10 100 1000 1
5 1 6 7 1 1 10 1


## Sample Output

5 7 -1 -1


## Discussion

It is not difficult to develop a divide-and-conquer algorithm checking whether a given array of size $n$ contains a majority element in $O(n \log n)$ time. It is interesting to note that there is also a linear time algorithm and it is also based on divide-and-conquer.