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