Find majority element in an array

Problem - You have to find a majority element in an array . An element is majority element if it occurs more than half times the size of array.

Solution -

1. Take two variables ,major which will contain majority element at the end and another count variable.
2. Initialize major to first element of the array and set count to one.
3. Now traverse the rest of array from the 2nd element.
4. For each array element a[i] ,
   

   if ( major==a[i] )
   count++;
   else if ( count == 0 )
   {
   major=a[i];
   count=1;
   }
   else
   count--;
   

5. At the end of traversing the array, major will consist of majority element.

Example:

A A A C C B B C C C B C C

1. initially, major=A , count =1; Now traverse the rest of the array
2. major=A , count=2
3. major=A , count=3
4. major=A , count=2
5. major=A , count=1
6. major=A , count=0
7. major=B , count=1
8. major=B , count=0
9. major=C , count=1
10. major=C , count=2
11. major=C , count=1
12. major=C , count=2
13. major=C , count=3finally majority element = C