Searching and Sorting: Find the majority element in the array

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 <algorithm>  
#include <iostream>    
#include <string>
#include <stack>
#include <vector>
#include <unordered_map> 
#include <queue> 

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<int, int> 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<<endl;
            break;
        }
    }
    
    if(count == 0)
        cout << "No Majority element" << endl;
}

int main()
{
    int arr[] = { 1, 1, 2, 1, 3, 5, 1 };
    int n = sizeof(arr) / sizeof(arr[0]);
 
    find_majority_element_brute_force(arr, n);
    find_majority_element_hash_map(arr, n);
 
    return 0;
}

Output:

The majority element using brute force approach is 1
The majority element using hash map approach is 1

Write a Comment

Leave a Comment

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