Home Arrays Find the majority element in an array. (Method 3)

Find the majority element in an array. (Method 3)

by nikoo28
4 comments

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

We discussed the basic 2 methods to approach this problem here:-

It is recommended to have a look at these 2 methods before proceeding with this one. This is the most optimized method and with least space complexity.
Since only one majority element is possible, we can use a simple scan of the input array and keep a track of the count of elements. We basically do not need to keep a count of every element in the array. We first find out the element, that is occurring the maximum times in an array and then we check if its the majority element.
Here is the process:-

  • Start from the first element of the array and initialize the count to be = 1, and set it as the majority candidate.
  • Start scanning the array.
    • If we get the same element as the majority candidate, then increment the count.
    • If we get a different element, decrease the count by 1.
    • At any moment, if the count is set to 0, that means we have a new majority candidate. Change the majority candidate to the current element and reset the count to 1. This is also known as the Moore’s Voting Algorithm. “Basic idea of the algorithm is if we cancel out each occurrence of an element e with all the other elements that are different from e then e will exist till end if it is a majority element. “
    • At the end of the array we will get a majority candidate.
  • Now that we have a majority candidate, just scan through the array and see if it appears more than (n/2) times. If yes, this is our majority element.

Here is the implementation of the above algorithm.

#include<stdio.h>

// function to find the majority candidate in a array arr
int findMajorityCandidate(int arr[], int size)
{
	// maj_index - to keep a track of majority candidate
	int maj_index = 0, count = 1;
	int i;

	for(i = 1; i < size; i++)
	{
		// if the element is same as majority candidate
		// increment count
		if(arr[maj_index] == arr[i])
		{
			count++;
		}
		// else, decrease count
		else
		{
			count--;
		}

		// at any time if count becomes 0
		if(count == 0)
		{
			// change the majority cadidate
			maj_index = i;
			count = 1;
		}
	}

	// return the majority candidate
	return arr[maj_index];
}

// a function to print the majority element
void printMajorityElement(int arr[], int size)
{
	// find the majority element
	int candidate = findMajorityCandidate(arr,size);

	int i, count = 0;

	// count the number of occurrences
	for (i = 0; i < size; i++)
	{
		if(arr[i] == candidate)
			count++;
	}
	if (count > size/2)
		printf("Majority element = %d",candidate);
	else
		printf("No majority element found");
}

int main(void)
{
	int arr[] = {8, 16, 8, 4, 8, 8, 8, 42, 16, 15, 8, 23, 4, 8, 15, 8, 8};

	printMajorityElement(arr, 17);

	return 0;
}

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

You may also like

4 comments

viki April 1, 2015 - 09:07

First part of the method will not give correct candidate if there is no majority element. In case of (2,2,2,3,4,5,6,7) it will return index 7 but it is supposed to return index 0.

Reply
nikoo28 April 2, 2015 - 01:58

Hi viki,

You have not understood the solution properly. You need to scan the array once again to check for the majority element.
The solution is absolutely correct. Here is the running link with your input:-
http://ideone.com/sV31xR

Reply
Igor March 20, 2015 - 02:50

It can be solved with bocketSort, although it’s not the best space complexity.

Reply
nikoo28 March 21, 2015 - 12:38

Hi Igor,

I will be glad, if you could post a solution using Bucket sort.

Reply

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