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.

Source: Algorithms by Dasgupta, Papadimitriou, Vazirani. McGraw-Hill. 2006.

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

Discussionclick to expand

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.