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.

Answer 2

st0le answered the question, but here's a 5minute implementation:

#include <stdio.h>  #define SIZE 13  int boyerMoore(int arr[]) {     int current_candidate = arr[0], counter = 0, i;     for (i = 0; i < SIZE; ++i) {         if (current_candidate == arr[i]) {             ++counter;             printf("candidate: %i, counter: %i\n",current_candidate,counter);         } else if (counter == 0) {             current_candidate = arr[i];             ++counter;             printf("candidate: %i, counter: %i\n",current_candidate,counter);         } else {             --counter;             printf("candidate: %i, counter: %i\n",current_candidate,counter);         }     }     return current_candidate; }  int main() {     int numbers[SIZE] = {5,5,5,3,3,1,1,3,3,3,1,3,3};     printf("majority: %i\n", boyerMoore(numbers));     return 0; } 

And here's a fun explanation (more fun than reading the paper, at least): http://userweb.cs.utexas.edu/~moore/best-ideas/mjrty/index.html