- Write a program to find the majority element of an array.
- C program to find majority element using Moore’s Voting Algorithm.

Given an integer array of size N. We have to **find the majority element of given array**.

*In an array of size N, a majority element appears more than N/2 times.*

For Example :

Input Array : 4 2 8 7 2 1 2 2 2

Majority Element is 2

**Method 1 : Brute Force**

Let inputArray be an integer array of size N.

- Count of frequency of each element of array using two for loop.
- Outer for loop will fix one element(let's say K) and inner for loop will count the occurrences of K in inputArray.
- If count of K is more than N/2 then K is a majority element.
- If we don't find any element whose count is > N/2 then inputArray doesn't contain any majority element.

^{2})

**Method 2 : By Sorting input array**

Let inputArray be an integer array of size N.

- Sort inputArray using any nLogn average time sorting algorithm like quick sort, merge sort etc.
- After sorting all identical elements will group together in adjacent locations.
- Traverse inputArray and find the count of identical adjacent element.
- If we found any element whose count is more than N/2 then same is a majority element.

**Method 3 : Using Moore’s Voting Algorithm**

Let inputArray be an integer array of size N. This approach is a two step method as follows:

- Using Moore's voting algorithm, find a potential candidate for majority element. This step returns a element occurring maximum number of times in array(let this element be K).
- Second step is to verify whether K is actually majority element or not. We will traverse inputArray and count the frequency of K. If it is more than N/2 then it is majority element else no majority element exists in inputArray.

Moore’s Voting Algorithm: We will cancel out each occurrence of K for all other element other than K. If count of K is non zero till end of array then K is a majority element.

- Assume first element of array is majority element and initialize the count of majority element to 1. Traverse inputArray from index 0 to N-1.
- If current element is equal to majority element then increment count else decrement count.
- If count is equal to zero then set current element as majority element and count as 1.

## C program to find majority element of array

#include <stdio.h> #define ARRAY_SIZE 100 void getMajorityElement(int *array, int size) { int i, majorityIndex = 0, count = 1; /* Find Majority Element */ for(i = 1; i < size; i++) { /* Check if current element is same as majority element, If yes then increment count otherwise decrement count */ if(array[majorityIndex] == array[i]) count++; else count--; if(count == 0) { majorityIndex = i; count = 1; } } /* Verify, If array[majorityIndex] is the majority element */ count = 0; /* Count the frequency of array[majorityIndex] in array */ for (i = 0; i < size; i++) { if(array[i] == array[majorityIndex]) count++; } /* Check if count of majority element is more than size/2, If yes, then it is a majority element otherwise not */ if(count > (size/2)) printf("Majority Element : %d\n", array[majorityIndex]); else printf("No Majority Element Found\n"); } int main(){ int i, array[ARRAY_SIZE], count, sum; printf("Enter the number of elements in Array\n"); scanf("%d", &count); printf("Enter %d numbers\n", count); for(i = 0; i < count; i++){ scanf("%d", &array[i]); } getMajorityElement(array, count); return 0; }Output

Enter the number of elements in Array 9 Enter 9 numbers 4 2 8 7 2 1 2 2 2 Majority Element : 2

Enter the number of elements in Array 9 Enter 9 numbers 4 2 8 7 2 1 2 1 3 No Majority Element Found