Coders Packet

Boyer-Moore majority vote algorithm in C++

By Vaishnavi Jaiswal

In this packet, you will learn about the implementation of the Boyer-Moore majority vote algorithm using C++ programming language.

Hey everyone,

Let's suppose you're given an array of size n and you have to print an element that occurs more than n/2 times in this array. There is at most one such element. It is also possible that the array doesn't contain any such element, in this case, return -1.

Now, you can start solving this problem using the brute force method. But we want a more efficient solution to this problem. Hence, we will use the Boyer-Moore majority vote algorithm for faster execution because it has better time complexity and is more efficient as compared to the traditional brute force method. Both of these approaches are explained below in detail.

Brute Force method                 

In the brute force method, we iterate over the array and then iterate again for each element to count its occurrences. For this purpose, we use two for loops, one inside the other. If the same element is found, we increment the count. Then, we compare the value of count with n/2 where n is the size of the array. If the count is greater than n/2, we return the corresponding element. If there is no such element present in the array, return -1.                  The brute force method contains two nested for loops and each run for n iterations. So, the overall time complexity adds up to quadratic time complexity that is O(n^2) in the worst case. It does not allocate additional space proportional to the array size so, the space complexity is constant and is equal to O(1).

The C++ code for the above method is given below. Here, in the code, I took a vector instead of an array. It doesn't matter whether you take a vector or an array. The only thing that matters is it should be a sequence of elements.

#include <bits/stdc++.h>
using namespace std;
 
//Brute force method
//Function to find the required element,it has two parameters, a vector and an integer(size of the vector)
/**Here I took vector instead of array,it doesn't matter whether it
is a vector or an array,the only thing that matters is it should be a sequence**/ int requiredElement(vectorv, int n) { for (auto x : v) { int count = 0; for (auto y:v) { if (x == y) count++; } // if count is greater than n/2 // return the corresponding element if(count>n/2){ return x; } } //else return -1 that means no such element is present return -1; } // Driver code int main() { vector v = {2,2,1,1,1,2,2}; int n = v.size(); // Function calling int ans=requiredElement(v,n); cout<<"The element that occurs more than n/2 number of times in this array is "<<ans; return 0; }

Boyer-Moore majority vote algorithm

The Boyer-Moore majority vote algorithm is used to find the element that appears more than n/2 times in a sequence of elements using linear time and constant space.                                                                                                                                                                                               This algorithm first declares two variables, an element, and a counter, with the counter initially equal to zero. It then iterates over each element of the array using for loop. Inside the loop for each element x, we check if the value of the counter is equal to zero or not, if yes, the algorithm stores x as its required element. Otherwise, it compares x to the stored element(candidate), then it increments the counter, else it decrements the counter. When the algorithm terminates, if the array has an element that appears more than n/2 times, it will be the element stored by the algorithm and will be returned by the function. Even when the array contains no such element, the algorithm will return one of the elements as its result. However, we can perform a second pass over the same array to count the number of times the returned element occurs and determine whether is actually the required element. The second pass is required as it is not possible to determine whether the required element exists just by a single pass through the array.            Boyer-Moore algorithm performs constant work exactly n times, so the overall time complexity of this algorithm is linear that is O(n). It allocates only constant additional memory. Hence, the space complexity is constant and is equal to O(1).

C++ code for the implementation of the Boyer-Moore majority vote algorithm is given below. Here, in the code, I took a vector instead of an array. It doesn't matter whether you take a vector or an array. The only thing that matters is it should be a sequence of elements.

#include <bits/stdc++.h>
using namespace std;

//Boyer-Moore majority vote algorithm to find the required element
/**This function returns the element which occurs more than n/2 times in the  array,it has two parameters, a vector and an integer(size of the vector)**/
/**Here I took vector instead of array,it doesn't matter whether it 
is a vector or an array,the only thing that matters is it should be a sequence**/
int Boyer_Moore(vectorv,int n) {
        int count = 0;
        int candidate=0;
        for (auto x: v) {
            if (count == 0) {
                candidate = x;
            }
            if(x==candidate){
                count++;
            }
            else{
                count--;
            }
        }

        return candidate;
    }
//Driver code
int main()
{
    vector v = {2,2,1,1,1,2,2};
    int n = v.size();
 
    // Function calling
    int ans=Boyer_Moore(v,n);
    cout<<"The element that occurs more than n/2 number of times in this array is "<<ans;
 
    return 0;
}

 

Download project

Reviews Report

Submitted by Vaishnavi Jaiswal (Vaishnavi0904)

Download packets of source code on Coders Packet