A majority element in an array A, of size N is an element that appears more than N/2 times (and hence there is atmost 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
1 comment:
Program:
First pass:
----
count = o
elem = -1
for(i=0 to n-1)
{
if(count==0)
{
elem = a[i];
count += 1;
}
else
{
if ( a[i] == elem ) ++count;
else --count;
}
}
----
In the second pass, check if the "elem" above is the majority element
Post a Comment