Find the majority element in the array – ProDeveloperTutorial.com – The Global Tofay

Problem Statement:

You are given an arrya of repeating elements. You need to find and print the majority element.

An element that appears more tha n/2 times, is called as majority element.

Example

Input : {3, 3, 4, 2, 4, 4, 2, 4, 4}
Output : 4

4 is repeated 5 times that is greater than the half of the size of the array.

Solution

Method 1: Brute Force Approach

Create 2 loops, and then keep track of the maximum count for all the different elements.
If the count become greater than n/2 times break the loop and return the element.

Method 2: Using hash map

A hashmap is a key value pair. Here the key is the element, and the value is the number of times the element is repeated.

Solution in C++

#include   
//visit www.ProDeveloperTutorial.com for 450+ solved questions  
#include     
#include 
#include 
#include 
#include  
#include  

using namespace std;

void find_majority_element_brute_force(int arr[], int n)
{
    int maxCount = 0;
    int index = -1; 

    for (int i = 0; i < n; i++) 
    {
        int count = 0;
        for (int j = 0; j < n; j++) 
        {
            if (arr[i] == arr[j])
                count++;
        }

        if (count > maxCount) 
        {
            maxCount = count;
            index = i;
        }
    }
 
    if (maxCount > n / 2)
        cout << "The majority element using brute force approach is "<< arr[index] << endl;
 
    else
        cout << "No Majority Element" << endl;
}

void find_majority_element_hash_map(int arr[], int size)
{
    unordered_map m;

    for(int i = 0; i < size; i++)
        m[arr[i]]++;
    
    int count = 0;
    
    for(auto i : m)
    {
        if(i.second > size / 2)
        {
            count =1;
            cout << "The majority element using hash map approach is " << i.first<
Output:
 
The majority element using brute force approach is 1
The majority element using hash map approach is 1