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])
		if(count > (size/2))
			found = 1;
			majority = arr[i];
		printf("Majority element = %d",majority);
		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

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