Finding Majority Element in an Array in JAVA Language

June 11, 2020

Finding Majority Element in an Array

A Majority Element in an array is a element whose frequency in the array is greater then the half of the length of the array. For Ex. Arr={1, 2, 1, 1, 4, 3, 4, 4, 4, 4, 4, 3} , Here n(length of the array) = 11, n/2 = 5, Frequency of 4 is 6 ie. > n/2. So, the majorityelement in this array is 4.

Explanation

Keep the track of the maximum count for all the different elements using two loops. If the maximum count becomes greater than half of the length of the given array, then break out of the loops and return the element which has the maximum count. If the maximum count is less than half the length of the given array, it means that the majority element isn’t present.

Algorithm

To store the max count create a variable count and initiate it with 0
Use a loop to traverse through the array, run another loop for every element to find the count of similar elements in the same array.
If the max count is less than the count of elements in the array, change the value of max count to count and store the index of that element in a different variable.
If the maximum count reaches a value greater than half of the length of the array then print the element.
If the case is not the same print there is no majority element

import java.io.*;
import java.util.*; 
public class Main
{
static void maj(int arr[], int n)  
{  
    int c = 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 > c)  
        {  
            c = count;  
            index = i;  
        }  
    } 
    if (c > n/2)  
    System.out.println (arr[index]);  
    else
    System.out.println ("No Majority Element");  
}

    public static void main (String[] args) { 
        Scanner s= new Scanner(System.in);
        System.out.println("Enter length of the array");
        int l=s.nextInt();
        System.out.println("Enter the elements of the array");        
        int[] arr= new int[l]; 
        for(int i=0; i<l; i++)
            arr[i]=s.nextInt();
        System.out.println("Majority Element is: ");
        maj(arr, l);  
    } 
}

Enter length of the array
5
Enter the elements of the array
1
3
4
1
1
Majority Element is: 
1