Question

How do you write a java program that implements Majority-Element using Boyer & Moore approach?

Answer 1

CODE

import java.util.Scanner;

public class Main

{

public static void printMajorityElement(int a[])

{

int size = a.length;

int cand = findCandidate(a, size);

if (isMajority(a, size, cand))

System.out.println("Majority element is: " + cand);

else

System.out.println("-1");

}

public static 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];

}

public static 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;

}

public static void main(String[] args)

{

Scanner sc = new Scanner(System.in);

int n;

System.out.println("Enter the number of elements: ");

n = sc.nextInt();

int a[] = new int[n];

System.out.println("Enter the array elements separated by space: ");

for (int i=0; i<n; i++) {

a[i] = sc.nextInt();

}

printMajorityElement(a);

sc.close();

}

}