Finding the max repeated element in an array

Question

Given an array with N elements. We know that one of those elements repeats itself atleast N/2 times . We dont know anything about the other elements . They may repeat or may be unique .

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

P.S : No extra space is to be used .

Answer 1

The Boyer-Moore Majority Vote Algorithm

lst = [1,2,1,2,3,1,3,3,1,2,1,1]
currentCount = 0
currentValue = lst[0]
for val in lst:
   if val == currentValue:
      currentCount += 1
   else:
      currentCount -= 1

   if currentCount == 0:
      currentValue = val
      currentCount = 1


print(currentValue)

Answer 2

It doesn't seem possible to count anything without using extra space. You have to store atleast one counter somewhere. If you mean to say you cannot use more than O(n) space then it should be fairly easy.

One way would be to create a second list of only unique objects from the original list. Then, create a third list the same length as the second with a counter for the number of occurrences of each item in the list.

Another way would be to sort the list then find the largest contiguous section.

Answer 3

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;
}

void main() {
    int numbers[SIZE] = {5,5,5,3,3,1,1,3,3,3,1,3,3};
    printf("majority: %i\n", boyerMoore(numbers));
}

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

Answer 4

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.