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;
}
Comments
Decent first post.

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

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!

Edited 6 Years Ago by GillBates: n/a

> 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.

Comments
nice explanation

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.

This article has been dead for over six months. Start a new discussion instead.