## 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
```

## Thanks for reading!

If you have any questions about the post feel free to leave a comment below.

Follow me on twitter: @soorya_54

## Discussion (0)