Find Majority Element of an Array

Find Majority Element of an Array” is one of the most favorite technical interview problem based on array data structure. Here, we are given an array of size ‘n’ and our task is to find the majority element of the array. 

If there is no majority Element, print a message “No majority element”.

A majority element of the array is the element which appears more than (n/2) elements.

Example:

INPUT:
Arr[5] = {3, 1, 3, 2, 3}
OUTPUT:
3
INPUT:
Arr[5] = {1, 2, 3, 4, 5}
OUTPUT:
No majority element

There are many ways to find majority element of the array. Some of the ways are:

METHOD 1: Brute – force

The steps required to find majority element of the array are as follows:

  1. Scan array size.
  2. Scan array elements.
  3. Now, count occurrence of each element of the array using two nested for loops.
  4. While counting occurrence of each element, also check if the count more than (n/2) or not. If for any element the count is more than (n/2), print the resultant element.

C++ Program to find majority element of the array is as follows:

/* Program to find the majority element */  
#include<bits/stdc++.h>  
using namespace std;  
int main()  
{  
    /* Scan array size */  
    int n;  
    cout<<"Enter array size:";  
    cin>>n;  
      
    /*Scan array elements */  
    int arr[n];  
    cout<<"\nEnter array elements: ";  
    for(int i = 0; i < n; i++)  
    cin>>arr[i];  
      
    int res = -1;  
    /* Count frequency of each element */  
    for(int i = 0; i < n; i++)  
    {  
        int count = 0;  
        /* Count occurrence of each element of the array */  
        for(int j = 0; j < n; j++)  
        {  
            if(arr[i] == arr[j])  
            count++;  
        }  
        /* If count > (n/2), it's majority element */  
        if(count > (n/2))  
        {  
            res = arr[i];  
            break;  
        }  
    }  
    /* Print the result */  
    if(res == -1)  
    {  
        cout<<"\nNo majority element!!";  
    }  
    else  
    {  
        cout<<"\n"<<res<<" is majority element of the array!!";  
    }  
}  
OUTPUT:
Enter array size: 5
Enter array elements: 1 2 3 2 3
No majority element!!

Time Complexity:
O(n^2), where ‘n’ is the size of the array

METHOD 2: Using Hashing

The step required to find the majority element of the array are as follows:

  1. Scan array size.
  2. Scan array elements.
  3. Create a hashmap as (key = int) and (value = int).
  4. Iterate over all the elements of the array and increment count of each element in map.
  5. Now, scan the map and check count of each element, whether it is greater than (n/2) or not. If any element has a count greater than (n/2), it will be majority element. 

C++ Program to find majority element of the array is as follows:

/* Program to find the majority element */  
#include<bits/stdc++.h>  
using namespace std;  
int main()  
{  
    /* Scan array size */  
    int n;  
    cout<<"Enter array size:";  
    cin>>n;  
      
    /*Scan array elements */  
    int arr[n];  
    cout<<"\nEnter array elements: ";  
    for(int i = 0; i < n; i++)  
    cin>>arr[i];  
      
    int res = -1;  
      
    /* Create hash map */  
    map<int,int> mp;  
      
    /* Store count of each element */  
    for(int i = 0; i < n; i++)  
    {  
        mp[arr[i]]++;  
    }  
      
    /* Check count of each element */  
    map<int,int> :: iterator itr;  
    for(itr = mp.begin(); itr != mp.end(); ++itr)  
    {  
        if(itr->second > (n/2))  
        {  
            res = itr -> first;  
            break;  
        }  
    }  
      
    /* Print the result */  
    if(res == -1)  
    cout<<"No majority element!!";  
    else  
    cout<<res<<" is the majority element!!";  
  
}  

OUTPUT:
Enter array size: 5
Enter array elements: 2 1 2 3 2
2 is the majority element!!

Time Complexity: 
O(nlogn) , n for scanning array and logn for searching and incrementing the count of each element.

Related Posts:

  1. Program to find mean of the Array.
  2. Program to sort an Array of 0s and 1s.
  3. Program to merge two sorted arrays.
  4. Program to find missing number in an array.
  5. Program to sort if array is sorted.
  6. Program to print Alternate Elements of an Array.
  7. Program to swap kth element from beginning to kth element from end in an Array.
  8. Program to print all possible subarrays of the given array.
  9. Program to print kth smallest and kth largest element of an Array.
  10. Program to find equilibrium index of an Array.
  11. Program to Reverse an Array.
  12. Program to count number of odd numbers and even numbers in an array.
  13. Program to find absolute difference between sum of odd index elements and even index elements.
  14. Program to find smallest and largest element of the array.
  15. Program to count occurrences of a particular element in an array.
  16. Program to search an element in an Array (Linear Search).
  17. Program to Rotate Array Elements by ‘D’ positions.
  18. Program to find most frequent element in an array.
  19. Program to find pair in an array with given sum.
  20. Program to find first repeating element of an array.

You may also like...

Leave a Reply

Your email address will not be published. Required fields are marked *