35

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 .

8
  • 1
    Is this homework? If it is, please tag it as such.
    – Will A
    Commented Sep 18, 2010 at 4:25
  • No extra space can be used, or just O(1) space may be used? Iterating over an array must use some space.
    – Will A
    Commented Sep 18, 2010 at 4:26
  • @Will : It is not homework... I tried it enough but could not find a better way ...
    – Flash
    Commented Sep 18, 2010 at 4:30
  • 2
    Strictly speaking, this problem cannot be solved in O(1) space because the language is not regular. The counter variable required for any solution, takes O(log n) space. :-) Commented Sep 18, 2010 at 12:41
  • 1
    @R.. : That is technically correct....the best kind of correct!
    – Jim Lewis
    Commented Sep 18, 2010 at 23:24

8 Answers 8

58

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:

arrows radiating from the centre

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.

0
39

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

14
  • Thanks! Quite beautiful idea. (BTW, you would surely get some more upvotes if explained concept to everybody in plain English. It's not difficult at all.) Commented Sep 18, 2010 at 4:59
  • 7
    This algorithm satisfies the conditions of the question. However, one should keep in mind that it returns the potential majority item. If there is no majority, then the result is meaningless. Thus, if you are unsure, you have to loop a second time and see how many times that element actually appears.
    – Matthew
    Commented Sep 18, 2010 at 5:03
  • 3
    The question postulates that we know that one of those elements repeats itself *at least* N/2 times so if the data is well-formed, the algorithm will work every time. Commented Sep 18, 2010 at 5:04
  • 1
    +1 for a link to an excellent explanation of a brilliant algorithm I've never seen before. Commented Sep 18, 2010 at 5:45
  • 1
    @David, it's possibly incorrect, when assigining a new candidate, your count should be assigned =1
    – st0le
    Commented Sep 19, 2010 at 6:02
37

The Boyer-Moore Majority Vote Algorithm

//list needs to have an element with a count of more than n/2 throughout itself for
//this algorithm to work properly at all times.

lst = [1,2,1,2,3,1,3,3,1,2,1,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)
11
  • 1
    It's pretty simple, you could easily implement it.
    – st0le
    Commented Sep 18, 2010 at 4:28
  • pretty simple Care to explain to the rest of us? Commented Sep 18, 2010 at 4:39
  • Added an answer with a simple implementation. Commented Sep 18, 2010 at 4:52
  • @st0le: Your sample is not correct. You use the index i instead of the list value lst[i] in comparision as well as in assignment. Could you fix it?
    – harper
    Commented Sep 18, 2010 at 7:46
  • @harper, i contains the value itself...i guess, i convention threw you off. i'll rename it.
    – st0le
    Commented Sep 18, 2010 at 8:39
2

This code is a similar implementation to the way in which we find the majority of an element

int find(int* arr, int size)
{ 
int count = 0, i, m;
  for (i = 0; i < size; i++) 
  {
    if (count == 0)
        m = arr[i];
    if (arr[i] == m) 
        count++;
    else
        count--;
   }
    return m;
}
0

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.

2
  • +1 - probably not the optimal solution, but O(n log n) for the sort-based solution is a good trade-off versus complexity of other methods.
    – Will A
    Commented Sep 18, 2010 at 4:34
  • You aren't trying to count. You are trying to find a number that occurs at least half the time.
    – MSN
    Commented Sep 18, 2010 at 5:12
0

Using the modification suggested by ffao to Davi'd reply:

public class MaxRepeated {

    public static void main(final String[] args) {
        maxRepeatedElement(new int[]{1, 2, 1, 2, 3, 2, 3, 1});
        maxRepeatedElement(new int[]{1, 2, 1, 2, 3, 1, 3, 1});
        maxRepeatedElement(new int[]{1, 2, 1, 2, 4, 1, 1, 3, 1, 3, 1});
        maxRepeatedElement(new int[]{1, 2, 1, 2, 2, 1, 2, 3, 1, 2, 1, 2});
    }

    private static int maxRepeatedElement(final int[] arr) {

        int current_candidate = arr[0];
        int previous_candidate = arr[0];
        int counter = 0, i;
        for (i = 0; i < arr.length; ++i) {
            if (current_candidate == arr[i]) {
                ++counter;
            } else if (counter == 0) {
                previous_candidate = current_candidate;
                current_candidate = arr[i];
                ++counter;
            } else {
                --counter;
            }
            System.out.printf("  candidate: %d, counter: %d\n", current_candidate, counter);
        }

        if (counter == 0) {
            System.out.printf(" possible: %d or %d with net freq %d \n", current_candidate, previous_candidate, counter);
            final int f1 = frequency(arr, current_candidate);
            final int f2 = frequency(arr, previous_candidate);
            final int halfLen = arr.length / 2 + (arr.length % 2 == 0 ? 0 : 1);
            if (f1 >= halfLen || f2 >= halfLen) {
                if (f1 > f2) {
                    System.out.printf("majority: %d with freq %d \n", current_candidate, f1);
                } else {
                    System.out.printf("majority: %d with freq %d \n", previous_candidate, f2);
                }
            } else {
                System.out.printf("NO majority! \n");
            }
        } else {
            System.out.printf("majority: %d with freq %d \n", current_candidate, frequency(arr, current_candidate));
        }
        return current_candidate;
    }

    private static int frequency(final int[] arr, final int candidate) {
        int counter = 0;
        for (int c : arr) {
            counter += candidate == c ? 1 : 0;
        }
        return counter;
    }
}
0

Try this :

#include<iostream>
using namespace std;
int main()
{
    int counter=0;
    int a[]={10, 11, 5, 27, 4, 2, 7, 5, 7, 11, 9, 5, 5, 4, 10, 7, 5, 3, 7, 5};
    for(int i = 0; i < 20; i++)
    {
        if(a[i]==5)
        counter++;
    }
    cout << "it appears " << counter << " times";
}
1
  • 1
    How does this answer the problem. This only shows you the number of fives. It does not find which number has the most repeats. Commented Jan 22, 2016 at 17:49
-2

The Boyer-Moore Majority Vote Algorithm fails to find correct majority in the below input arrays

int numbers[SIZE] = {1,2,3,4,1,2,3,4,1,2,3,4};

int numbers[SIZE] = {1,2,3,4,1,2,3,4,1,2,3,4,1};

1
  • 3
    The algo works if at least one element repeats itself n/2 times. Commented Sep 3, 2013 at 4:23

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.