Boyer–Moore majority vote algorithm in C

Boyer-Moore majority vote algorithm

Boyer–Moore majority vote algorithm is one of the popular optimal algorithms which is used to find the majority element among the given elements of the array, that have more than N/ 2 occurrences. Boyer–Moore’s majority vote algorithm works perfectly fine for finding the majority element which takes 2 traversals over the given elements, which works in O(N) time complexity and O(1) space complexity.

Boyer-Moore majority vote algorithm in C

Algorithm :

  • Take the size of the array and store it in variable n.
  • Take n elements of the array from the user.
  • Declare two variables one is maj_index and initialize it with 0, and one variable count with value 0.
  • Run a loop from index 1 to n-1
  • Check if a[i]==a[maj_index] then increase the value of count by 1, else decrease it by 1.
  • If count becomes zero then set maj_index=i and count =1.
  • Now create one function check that will check whether the maj_index value presents n/2 times or not.
  • If it is present then return 1, otherwise 0(means no elements present more than n/2 times).

Sample Test Case:

  • Input: k = 6,  arr = [ 1, 2, 5, 2, 2, 2 ]
  • Output: Majority Element is 2

C code

Run
#include<stdio.h>

int find_majority( int a[], int size)
{ 
    int maj_index=0, count=1;
    
    for(int i=1; i<size; i++)
    {
        if(a[i]==a[maj_index])
            count++;
        else
            count--; 
        
        if(count==0)
        {
            maj_index=i;
            count=1;
        }
    }
    return a[maj_index];
}

int check_maj(int a[], int n , int k)
{ 
    int count=0;
    
    for(int i=0;i<n;i++) { if(a[i]==k) count++; } if(count>n/2)
        return 1;
    else
        return 0;
}

int main() 
{
    int k,n;
    scanf("%d", &n);
    
    int a[n];
    for(int i=0; i<n; i++)
        scanf("%d", &a[i]);

    k = find_majority( a,n);
    
    if(check_maj(a,n,k))
        printf("Majority element is %d", k);
    else
        printf("No Majority element\n");
    
    return 0;
}

Output:

 Majority Element is 2