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.

Java Program to find the Majority Element in an Array
JAVA Program to find Majority Element in an Array

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

  1. To store the max count create a variable count and initiate it with 0
  2. 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.
  3. 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.
  4. If the maximum count reaches a value greater than half of the length of the array then print the element.
  5. 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