# Checking whether at least n/2 + 1 elements of a set/vector are equal

We have a set of elements, say a vector of $n$ elements (actually, the data structure really doesn't matter in this case). It is NOT sorted. We want to check whether at least $n/2 + 1$ elements are equal.

I have been thinking about an efficient algorithm to do so but I don't know, the fact that it is not sorted makes it quite difficult for me.

If it was sorted, we could do it with an $O(n)$ algorithm, I'd say: just iterate over the vector, saving the most common element. If the counter arrives to $n/2 + 1$, we are done.

Could you give me some advice? Thank you very much.

• This is a standard exercise -- I suggest you think about it some more, especially in the context of the course in which it was set. – David Richerby Oct 3 '17 at 11:11
• Thanks for your answer. Could you give me a hint, at least? What about Hoare's selection to find the median (O(log(n)), and then checking how many times does this element appear? This would be O(log(n) + n), but I'm being asked to find a O(nlog(n)). – Jose Oct 3 '17 at 11:19
• An algorithm which runs in time $O(\log n + n)$ also runs in time $O(n\log n)$. – Yuval Filmus Oct 3 '17 at 13:56
• @Jose If all you want is an $O(n\log n)$ algorithm, just sort the list. Hoare's selection algorithm requires at least linear time (you can't possibly find the $k$th-largest element of a list without looking at every element) and may take quadratic time in the worst case. – David Richerby Oct 3 '17 at 15:13
• (Not knowing what David Richerby is thinking of,) First hint: $O(n)$ does not mean/imply single pass. (Errm - $O(nlogn)$? Well, sure includes $O(n)$.) – greybeard Oct 3 '17 at 19:31

1. The element you are looking for will also be the median of the list. Find the median of the list using the Median of Medians algorithm. $O(n)$ complexity
2. Check if the median appears at least $n/2 + 1$ times on the list $O(n)$ complexity
• I'm not sure the condition $count=n/2+1$ is correct. If the array consists of $n/2+1$ copies of $x$ followed by $n/2-1$ copies of $y$, you will get 2 at the end. – Yuval Filmus Oct 3 '17 at 18:48