Home Arrays Find the majority element in an array.

Find the majority element in an array.

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

Method 2:- Using sorting
Method 3:- Using a single scan

You may also like

Enclose codes in [code lang="JAVA"] [/code] tags

This site uses Akismet to reduce spam. Learn how your comment data is processed.

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