Majority Element

Question: A majority element in an array A[] of size n is an element that appears more than n/2 times (and hence there is at most one such element).

Write a function which takes an array and emits the majority element (if it exists), otherwise prints NONE as follows:

I/P : 3 3 4 2 4 4 2 4 4
O/P : 4

I/P : 3 3 4 2 4 4 2 4
O/P : NONE

Algo:
This is a two step process.
1. Get an element occurring most of the time in the array. This phase will make sure that if there is a majority element then it will return that only.
2. Check if the element obtained from above step is majority element.

Step#1:
findCandidate(a[], size)
1. Initialize index and count of majority element
maj_index = 0, count = 1
2. Loop for i = 1 to size – 1
(a)If a[maj_index] == a[i]
count++
(b)Else
count–;
(c)If count == 0
maj_index = i;
count = 1
3. Return a[maj_index]

Step#2:
Check if the element obtained in step 1 is majority

printMajority (a[], size)
1. Find the candidate for majority
2. If candidate is majority. i.e., appears more than n/2 times.
Print the candidate
3. Else
Print “NONE”

Solution:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30

int findMajority(int[] a)     {         int count, major;               count=0;         major=0;                for(int i=0; i<a.length; i++){             if(count==0){                 major=a[i];                 count=1;             }             else if(a[i] == major){                 count++;             }             else{                 count--;             }         }               return major;     }           boolean isMajority(int[] a, int majNum) {                   int count=0, size=a.length;         for(int i=0; i<size; i++) {             if(a[i]==majNum) {                 count++;             }         }         return (count>size/2)?true:false;     }