Home Arrays Find the majority element in an array.

# Find the majority element in an array.

0 comment

Question: An element is a majority if it appears more than n/2 times. Give an algorithm that takes an array of n elements and finds the majority element in that array. The array is not sorted.

Input: 8, 16, 8, 4, 8, 8, 8, 42, 16, 15, 8, 23, 4, 8, 15, 8, 8.
Output: Majority Element = 8

The most basic method of solving this problem is to take two loops and maintain a count of each of the element. If the count reaches more than (n/2) for any element, break the loop and return.

void printMajorityElement(int arr[], int size)
{
int count = 0;
int i,j;
int majority = 0;
int found = 0;

for(i = 0;i<size;i++)
{
count = 0;
for(j = 0;j<size;j++)
{
if(arr[i] == arr[j])
count++;
}
if(count > (size/2))
{
found = 1;
majority = arr[i];
break;
}
}

if(found)
printf("Majority element = %d",majority);
else
printf("Majority element not present");
}


Time Complexity:- O(n2)
Space Complexity:- O(1)

Note: There can only be one majority element in an array.

#### You may also like

This website uses cookies to improve your experience. We'll assume you're ok with this, but you can opt-out if you wish. Accept Read More