Majority Element Using Moore’s Voting Algorithm

This is a two-step process:

The first step gives the element that may be the majority element in the array. If there is a majority element in an array, then this step will definitely return majority element, otherwise, it will return candidate for majority element.
Check if the element obtained from the above step is the majority element. This step is necessary as there might be no majority element.

Illustration:

arr[] = {3, 4, 3, 2, 4, 4, 4, 4}, n = 8

maj_index = 0, count = 1

At i = 1: arr[maj_index] != arr[i]

count = count – 1 = 1 – 1 = 0
now count == 0 then:
maj_index = i = 1
count = count + 1 = 0 + 1 = 1
At i = 2: arr[maj_index] != arr[i]

count = count – 1 = 1 – 1 = 0
now count == 0 then:
maj_index = i = 2
count = count + 1 = 0 + 1 = 1
At i = 3: arr[maj_index] != arr[i]

count = count – 1 = 1 – 1 = 0
now count == 0 then:
maj_index = i = 3
count = count + 1 = 0 + 1 = 1
At i = 4: arr[maj_index] != arr[i]

count = count – 1 = 1 – 1 = 0
now count == 0 then:
maj_index = i = 4
count = count + 1 = 0 + 1 = 1
At i = 5: arr[maj_index] == arr[i]

count = count + 1 = 1 + 1 = 2
At i = 6: arr[maj_index] == arr[i]

count = count + 1 = 2 + 1 = 3
At i = 7: arr[maj_index] == arr[i]

count = count + 1 = 3 + 1 = 4
Therefore, the arr[maj_index] may be the possible candidate for majority element.

Now, Again traverse the array and check whether arr[maj_index] is the majority element or not.

arr[maj_index] is 4

4 occurs 5 times in the array therefore 4 is our majority element.

Follow the steps below to solve the given problem:

Loop through each element and maintains a count of the majority element, and a majority index, maj_index
If the next element is the same then increment the count if the next element is not the same then decrement the count.
if the count reaches 0 then change the maj_index to the current element and set the count again to 1.
Now again traverse through the array and find the count of the majority element found.
If the count is greater than half the size of the array, print the element
Else print that there is no majority element

Below is the implementation of the above idea:

C++

// C++ Program for finding out
// majority element in an array 
#include <bits/stdc++.h>
using namespace std;

/* Function to find the candidate for Majority */
int findCandidate(int a[], int size)
{
    int maj_index = 0, count = 1;
    for (int 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];
}

/* Function to check if the candidate
   occurs more than n/2 times */
bool isMajority(int a[], int size, int cand)
{
    int count = 0;
    for (int i = 0; i < size; i++)

        if (a[i] == cand)
            count++;

    if (count > size / 2)
        return 1;

    else
        return 0;
}

/* Function to print Majority Element */
void printMajority(int a[], int size)
{
    /* Find the candidate for Majority*/
    int cand = findCandidate(a, size);

    /* Print the candidate if it is Majority*/
    if (isMajority(a, size, cand))
        cout << " " << cand << " ";

    else
        cout << "No Majority Element";
}

/* Driver code */
int main()
{
    int a[] = { 1, 3, 3, 1, 2 };
    int size = (sizeof(a)) / sizeof(a[0]);

    // Function calling
    printMajority(a, size);

    return 0;
}

/* Program for finding out majority element in an array */
#include <stdio.h>
#define bool int

int findCandidate(int*, int);
bool isMajority(int*, int, int);

/* Function to print Majority Element */
void printMajority(int a[], int size)
{
    /* Find the candidate for Majority*/
    int cand = findCandidate(a, size);

    /* Print the candidate if it is Majority*/
    if (isMajority(a, size, cand))
        printf(" %d ", cand);
    else
        printf("No Majority Element");
}

/* Function to find the candidate for Majority */
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];
}

/* Function to check if the candidate occurs more than n/2
 * times */
bool 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 1;
    else
        return 0;
}

/* Driver code */
int main()
{
    int a[] = { 1, 3, 3, 1, 2 };
    int size = (sizeof(a)) / sizeof(a[0]);
  
    // Function call
    printMajority(a, size);
    getchar();
    return 0;
}

Java

/* Program for finding out majority element in an array */

class MajorityElement {
    /* Function to print Majority Element */
    void printMajority(int a[], int size)
    {
        /* Find the candidate for Majority*/
        int cand = findCandidate(a, size);

        /* Print the candidate if it is Majority*/
        if (isMajority(a, size, cand))
            System.out.println(" " + cand + " ");
        else
            System.out.println("No Majority Element");
    }

    /* Function to find the candidate for Majority */
    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];
    }

    /* Function to check if the candidate occurs more
       than n/2 times */
    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;
    }

    /* Driver code */
    public static void main(String[] args)
    {
        MajorityElement majorelement
            = new MajorityElement();
        int a[] = new int[] { 1, 3, 3, 1, 2 };
      
        // Function call
        int size = a.length;
        majorelement.printMajority(a, size);
    }
}

// This code has been contributed by Mayank Jaiswal

Python

# Program for finding out majority element in an array

# Function to find the candidate for Majority


def findCandidate(A):
    maj_index = 0
    count = 1
    for i in range(len(A)):
        if A[maj_index] == A[i]:
            count += 1
        else:
            count -= 1
        if count == 0:
            maj_index = i
            count = 1
    return A[maj_index]

# Function to check if the candidate occurs more than n/2 times


def isMajority(A, cand):
    count = 0
    for i in range(len(A)):
        if A[i] == cand:
            count += 1
    if count > len(A)/2:
        return True
    else:
        return False

# Function to print Majority Element


def printMajority(A):
    # Find the candidate for Majority
    cand = findCandidate(A)

    # Print the candidate if it is Majority
    if isMajority(A, cand) == True:
        print(cand)
    else:
        print("No Majority Element")


# Driver code
A = [1, 3, 3, 1, 2]

# Function call
printMajority(A)

// C# Program for finding out majority element in an array
using System;

class GFG {
    /* Function to print Majority Element */
    static void printMajority(int[] a, int size)
    {
        /* Find the candidate for Majority*/
        int cand = findCandidate(a, size);

        /* Print the candidate if it is Majority*/
        if (isMajority(a, size, cand))
            Console.Write(" " + cand + " ");
        else
            Console.Write("No Majority Element");
    }

    /* Function to find the candidate for Majority */
    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];
    }

    // Function to check if the candidate
    // occurs more than n/2 times
    static bool 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;
    }

    // Driver Code
    public static void Main()
    {

        int[] a = { 1, 3, 3, 1, 2 };
        int size = a.Length;
      
        // Function call
        printMajority(a, size);
    }
}

// This code is contributed by Sam007

Javascript

<script>
    // Javascript Program for finding out majority element in an array
    
    /* Function to print Majority Element */
    function printMajority(a, size)
    {
        /* Find the candidate for Majority*/
        let cand = findCandidate(a, size);
 
        /* Print the candidate if it is Majority*/
        if (isMajority(a, size, cand))
            document.write(" " + cand + " ");
        else
            document.write("No Majority Element");
    }
 
    /* Function to find the candidate for Majority */
    function findCandidate(a, size)
    {
        let maj_index = 0, count = 1;
        let 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];
    }
 
    // Function to check if the candidate
    // occurs more than n/2 times
    function isMajority(a, size, cand)
    {
        let i, count = 0;
        for (i = 0; i < size; i++) {
            if (a[i] == cand)
                count++;
        }
        if (count > parseInt(size / 2, 10))
            return true;
        else
            return false;
    }
    
    let a = [ 1, 3, 3, 1, 2 ];
    let size = a.length;

    // Function call
    printMajority(a, size);

// This code is contributed by rameshtravel07.
</script>

PHP

<?php
// PHP Program for finding out majority 
// element in an array 

// Function to find the candidate 
// for Majority 
function findCandidate($a, $size)
{
    $maj_index = 0;
    $count = 1;
    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];
}

// Function to check if the candidate
// occurs more than n/2 times 
function isMajority($a, $size, $cand)
{
    $count = 0;
    for ($i = 0; $i < $size; $i++)
    
    if ($a[$i] == $cand)
    $count++;
        
    if ($count > $size / 2)
    return 1;
    
    else
    return 0;
}

// Function to print Majority Element 
function printMajority($a, $size)
{
    /* Find the candidate for Majority*/
    $cand = findCandidate($a, $size);
    
    /* Print the candidate if it is Majority*/
    if (isMajority($a, $size, $cand))
        echo " ", $cand, " ";
    else
        echo "No Majority Element";
}

// Driver Code
$a = array(1, 3, 3, 1, 2);
$size = sizeof($a);

// Function calling
printMajority($a, $size);

// This code is contributed by jit_t
?>

Time Complexity: O(n), As two traversal of the array, is needed, so the time complexity is linear.
Auxiliary Space: O(1), As no extra space is required.

Majority Element

Find the majority element in the array. A majority element in an array A[] of size n is an element that appears more than n/2 times (and hence there is at most one such element).

Examples :

Input : A[]={3, 4, 2, 4, 2, 4, 4}
Output : 4
Explanation: The frequency of 4 is greater than the half of the size of the array size.

Input : A[] = {3, 3, 4, 2, 4, 4, 2, 4}
Output : No Majority Element
Explanation: There is no element whose frequency is greater than the half of the size of the array size.

Majority Element Using Moore’s Voting Algorithm

Majority Element

Categories

Contact US

Majority Element Using Moore’s Voting Algorithm

Majority Element

Similar Reads

Categories

Contact US