majority element (recursion)

[GillBates]

hello all

I'm trying to write a program that returns us majority element.
An array is said to have a majority element if more than half of its entries are the same - >(size of the array)/2.

It wouldn't be a problem if i had no conditions, but i have to write it in O(n log n) time complexity - so basically this means that i have to use recursive approach / quicksort algorithm.

I've found this code and tried to make it work but i just can't do it...
So, I'd be very grateful if someone could help me out (it seems that there's a problem in my recursion settings).

THANKS a lot!
p.s.: - please note that solution should be in O(n log n) time complexity.
- i have a basic knowledge about c++, so please forgive me if some of the errors in the code look "stupid".

#include <iostream>
using namespace std;

int majority(int *A, int inL, int inD)
{
    if(inD == 1)
        return A[0];

    int majorL = majority(A, inL, inD/2-1);
    int majorD = majority(A, inD/2+1, inD);

    int count = 0;
    for(int i=0; i<inD; i++)
        if(A[i] == majorL)
            count++;

    if(count > inD/2)
        return majorL;

    count = 0;
    for(int i=0; i<inD; i++)
        if(A[i] == majorD)
            count++;

    if(count > inD/2)
        return majorD;
    }
    return -1;
}

int main()
{
    int array[10] = {2,3,2,2,4,2,2,2,4,4};
    int indexL = 0;
    int indexD = 9;  //CHANGE IT IF YOU CHANGE ARRAY SIZE (indexD = ARRAY_SIZE - 1)!!!

    for(int i=0; i<10; i++)
        cout << array[i] << " ";

    int x = majority(array, indexL, indexD);

    if(x == -1)
        cout << "\n\nNo majority element!\n";
    else
    cout << "\n\nMajority element is: " << x << "\n";


    return 0;
}

[vijayan121]

You could do this in linear time; see Boyer and Moore's Voting Algorithm
http://www.cs.utexas.edu/users/moore/best-ideas/mjrty/index.html

#include <iostream>

int candidate_element( const int *array, int N )
{
    int count = 1 ;
    int curr_candidate = 0 ;

    for( int i = 1 ; i < N ; ++i )
    {
        if( array[i] == array[curr_candidate] ) ++count ;
        else --count ;

        if( count == 0 )
        {
            curr_candidate = i ;
            count = 1 ;
        }

    }
    return array[curr_candidate] ;
}

bool is_majority_element( const int *array, int N, int candidate )
{
  int cnt = 0 ;
  for( int i = 0 ; i < N ; ++i )
      if( array[i] == candidate ) ++cnt ;
  return cnt > N/2 ;
}


int main()
{
    int array[] = {2,3,2,2,4,2,2,2,4,4,4,4,4,4,2,2,2} ;
    enum { N = sizeof(array)/sizeof(*array) } ;

    int candidate = candidate_element( array, N ) ;

    if( is_majority_element( array, N, candidate ) )
        std::cout << "majority element: " << candidate << '\n' ;
    else
        std::cout << "there is no majority element\n" ;
}

[GillBates]

Thanks for your reply & help, vijayan121.
Solution that you posted is very good and interesting, but like i said, the algorithm has to have O(n log n) time complexity.

Any (other) ideas vijayan121? (please look at my above code - it would be very nice if someone could make it work because I'm kinda lost)

Thanks again!

[vijayan121]

> like i said, the algorithm has to have O(n log n) time complexity

Well, the Boyer and Moore's Voting Algorithm has a lower O(n) time complexity, clearly O(n) is better than O(n log n), isn't it?

Your algorithm has the right idea, it is a classic divide-and-conquer algorithm:

function majority( array A with number_of_elements N )
  if N == 1 : return A[0]
  let AL, AR be the first and second halves of A
  let ML = majority(AL)
  let MR = majority(AR)
  if neither half has a majority: return ‘‘no majority’’
  else:
       check whether either ML or MR is a majority element of A
       if so: return that element
       else: return ‘‘no majority’’

The idea is:
If A has a majority element X, then X appears more than N/2 times in A
Thus X appears more than N/4 times in either AL or AR.
So X must also be a majority element of either one or both of these two arrays.
Running time T(N) = 2 * T(N/2) + O(N) = O(N log N).

Your implementation has a few problems, here are a few hints:

int majorL = majority(A, inL, inD/2-1) ;
    int majorD = majority(A, inD/2+1, inD) ;

This partioning misses out the middle element inD/2, if inD is even

Consider inL == 5, inD == 9
majority(A, inL, inD/2-1) => majority(A, 5, 3) => inD < inL

Consider inL == 0, inD == 3
majority(A, inL, inD/2-1) => majority(A, 0, -1) => inD < inL && inD is -ve

Here is an implementation of the same idea(which uses zero-based arrays); with the information given above, and a look at this, you should be able to fix your code quite easily.

#include <iostream>
#include <algorithm>
using namespace std;

int majority( const int* A, int N )
{
    if( N == 1 ) return A[0] ;

    int mid = N/2 ;
    int majority_left = majority( A, mid ) ;
    int majority_right = majority( A+mid, N-mid ) ;

    if( majority_left == majority_right ) return majority_left ;
    if( count( A, A+N, majority_left ) > N/2 ) return majority_left ;
    if( count( A, A+N, majority_right ) > N/2 ) return majority_right ;
    return -1 ; // no majority
}

int main()
{
    int array[] = {2,3,2,2,4,2,2,2,4,4,2,4,4,4,4,2,4,2,2} ;
    enum { N = sizeof(array)/sizeof(*array) } ;

    int x = majority( array, N );

    if(x == -1) cout << "there is no majority element!\n" ;
    else cout << "majority element is: " << x << '\n' ;
}

There are at least two other ways to solve this problem in O(N log N) time:
a. Sort the array in O(N log N) time and then do a linear scan from the middle of the array in both directions to check if the middle element is a majority element.
b. Use a binary search tree eg. std::map<int,int>. Insert elements (keys) one by one into the map; if an element is already present then increment the count (data). At any stage, if the count becomes more than N/2 then that the key is the majority element.

There is also at least one other way to solve it in linear O(N) time:
Find the median of the array in linear time see: http://www.ics.uci.edu/~eppstein/161/960130.html
Count the number of occurrences of the median, if it is more than N/2, it is the majority element.

[GillBates]

Thank you very much for your help vijayan121!

[sbhikari]

Hi Vijyan,

Can we solve the Boyer and Moore's Voting Algorithm as said by you above using divide and conquer. So to solve the problem by o(n) using divide and conquer.

[kal_crazy]

http://xoax.net/comp_sci/crs/algorithms/lessons/Lesson4/

^you can follow that lesson page and get more information on quicksort. vijayan121 is correct.