c - How to find the element of an array that is repeated at least N/2 times?

Question

Given an array with N elements. We know that one of those elements repeats itself at least N/2 times.

We don't know anything about the other elements . They may repeat or may be unique .

Is there a way to find out the element that repeats at least N/2 times in a single pass or may be O(N)?

No extra space is to be used .

Answer 1

As the other users have already posted the algorithm, I won't repeat that. However, I provide a simple explanation as to why it works:

Consider the following diagram, which is actually a diagram of unpolarized light:

Each arrow from the centre represents a different candidate. Imagine a point somewhere on an arrow representing the counter and candidate. Initially the counter is at zero, so it begins in the centre.
When the current candidate is found, it moves one step in the direction of that arrow. If a different value is found, the counter moves one step towards the centre.
If there is a majority value, more than half of the moves will be towards that arrow, and hence the algorithm will end with the current candidate being the majority value.