Boyer-Moore’s Voting Algorithm

February 2, 2021

Boyer-Moore’s Voting Algorithm

Boyer-Moore’s Voting Algorithm  in Java:

Problem Statement

Imagine that you have a non-sorted list of values. You want to know if there is a value that is present in the list for more than half of the elements in that list. If so what is that value? If not, you need to know that there is no majority element. You want to accomplish this as efficiently as possible.

One common reason for this problem could be fault-tolerant computing. You perform multiple redundant computations and then verify that a majority of the results agree.

Given an array of size n, find the majority element. The majority element is the element that appears more than N/2 times.

Algorithm:

As per the above algorithm, we can divide out implementation into two parts

  1. The first iteration – Find the element which could be a majority element.
  2. The second iteration – check the element(found in the first iteration) count is greater than n/2

The first iteration – Find the element which could be a majority element

  • Say Array has 10 elements and say element x appears 6 times. Rest of the elements count = 4. If we start to cancel out each occurrence of x with the rest of the elements, still at the end we will have some count of x remaining. In our example (6-4 =2, x count )
  • Iterate through the array and maintain the count of majority_element.(starts with the first element in the array.)
  • If the next element is the same then increment the count
  • If next element is not same then decrement the count.
  • If count becomes zero then majority_element = current element, count =1.
  • After the first iteration, majority_element will be the candidate that might have the count > n/2.

The second iteration – check the element (found in the first iteration) count is greater than n/2

  • Iterate through the array and get the count of the element found in the first step. If the count is >n/2 then print it.
  • If count is less than n/2 then ignore it, array does not have majority element.

Time Complexity: O(n), Space Complexity: O(1)

Java code :

class prepinsta
{
    
    public static int findmajorityElement(int[] A)
    {
        // `m` stores the majority element (if present)
        int m = –1;
 
       
        int i = 0;
 
        // do for each element `A[j]` in the array
        for (int j = 0; j < A.length; j++)
        {
            // if counter `i` becomes 0
            if (i == 0)
            {
                // set the current candidate to `A[j]`
                m = A[j];
 
                
                i = 1;
            }
 
            
            else if (m == A[j]) {
                i++;
            }
           
            else {
                i–;
            }
        }
 
        return m;
    }
 
    public static void prepinsta (String[] args)
    {
       //function calling
        int[] arr = { 1,2,2,4,4,2,2,6,3 };
 
        System.out.println(“Majority element is “ + findmajorityElement(arr));
    }
}
Output:

Majority element is 2