*1.7K*

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)

## 4 comments

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.

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

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

Hi Igor,

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

Comments are closed.