Find the majority element in an array.

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(n²)
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