// Java program to find Majority
// element in an array
import java.io.*;
class GFG {
// Function to find Majority element
// in an array
static void findMajority(int arr[], int n)
{
int maxCount = 0;
int index = -1; // sentinels
for(int i = 0; i < n; i++)
{
int count = 0;
for(int j = 0; j < n; j++)
{
if(arr[i] == arr[j])
count++;
}
// update maxCount if count of
// current element is greater
if(count > maxCount)
{
maxCount = count;
index = i;
}
}
// if maxCount is greater than n/2
// return the corresponding element
if (maxCount > n/2)
System.out.println (arr[index]);
else
System.out.println ("No Majority Element");
}
// Driver code
public static void main (String[] args) {
int arr[] = {1, 1, 2, 1, 3, 5, 1};
int n = arr.length;
// Function calling
findMajority(arr, n);
}
//This code is contributed by ajit.
}
/* Program for finding out majority element in an array */
class MajorityElement
{
/* Function to print Majority Element */
void printMajority(int a[], int size)
{
/* Find the candidate for Majority*/
int cand = findCandidate(a, size);
/* Print the candidate if it is Majority*/
if (isMajority(a, size, cand))
System.out.println(" " + cand + " ");
else
System.out.println("No Majority Element");
}
/* Function to find the candidate for Majority */
int findCandidate(int a[], int size)
{
int maj_index = 0, count = 1;
int i;
for (i = 1; i < size; i++)
{
if (a[maj_index] == a[i])
count++;
else
count--;
if (count == 0)
{
maj_index = i;
count = 1;
}
}
return a[maj_index];
}
/* Function to check if the candidate occurs more
than n/2 times */
boolean isMajority(int a[], int size, int cand)
{
int i, count = 0;
for (i = 0; i < size; i++)
{
if (a[i] == cand)
count++;
}
if (count > size / 2)
return true;
else
return false;
}
/* Driver program to test the above functions */
public static void main(String[] args)
{
MajorityElement majorelement = new MajorityElement();
int a[] = new int[]{1, 3, 3, 1, 2};
int size = a.length;
majorelement.printMajority(a, size);
}
}
// This code has been contributed by Mayank Jaiswal