## DEV Community is a community of 847,300 amazing developers

We're a place where coders share, stay up-to-date and grow their careers. # Find majority element using Moore's Voting algorithm

## Majority Element

A majority element in an array of size n is an element that appears more than n/2 times and hence there is at most one such element. For example, the majority element of the array {1, 2, 1, 1, 3} is 1.

## Moore's voting algorithm

Moore's voting algorithm helps us find the majority element in an array using the following steps,

• Initialize a result variable with value 0 and a count variable with value 1
• Iterate through the array and increment the count variable if the element is same as result else decrement the count variable
• If the count variable becomes 0, then reset the count variable with value 1 and set result variable as the array element.
• Iterate through the array again and find the count of result variable from first iteration
• If result variable count is less than n/2 then return -1 else return the result variable as Majority Element

Let arr = {2, 3, 4, 2, 2, 5}, n = 6 ## Code

``````import java.io.*;
import java.util.*;

class Test {

// T(n) = Θ(n)
// Aux space = Θ(1)

public static int findMajority(int[] arr, int n) {
int res=0, count=1;
for(int i=0; i<n; i++) {
if(arr[i] == res) {
count++;
} else {
count--;
}

if(count == 0) {
count = 1;
res = arr[i];
}
}

count = 0;
for(int i=0; i<n; i++) {
if(arr[i] == res) {
count++;
}
}

if(count < n/2) {
return -1;
}

return res;
}

public static void main (String[] args) {
Scanner in = new Scanner(System.in);

int n = in.nextInt();
int[] arr = new int[n];
for(int i=0; i<n; i++) {
arr[i] = in.nextInt();
}

int res = findMajority(arr, n);
System.out.println(res);
}
}
``````

## Output

``````2
``````