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 

Thanks for reading!

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

Follow me on twitter: @soorya_54