Boyer-Moore Voting Algorithm - The Coding Shala

Home >> Algorithms >> Boyer Moore Voting Algorithm

 In this post, we will learn what is Boyer Moore Voting Algorithm and how to implement it.

Boyer-Moore Voting Algorithm

The Boyer-Moore Majority vote algorithm is an algorithm for finding the majority of a sequence of elements using linear time and constant space. [Wikipedia]

Approach 

Initially set the first element as the Majority element and count as 1 and move the pointer forward over an element[start loop from index 1]

  • if the count is 0 then, set the current element as the Majority element and count as 1.
  • if the current element is the same as the Majority element then increase the counter by 1.
  • if the current element is not the same as the Majority element then decrease the element by 1.
When we are done, the current Majority element is our answer.

let's take an example under this.

Find Majority Element Using Boyer Moore's Voting Algorithm

In the given array we are going to find out the majority element using Boyer Moore's voting algorithm

Example
Input: nums = [2,2,1,1,1,2,2]
Output: 2

Java Program: 

class Solution {
    public int majorityElement(int[] nums) {
        int count = 1;
        int majority = nums[0];
        for(int i=1; i<nums.length; i++) {
            if(count == 0) {
                majority = nums[i];
                count = 1;
            } else if(majority == nums[i]) count++;
            else count--;
        }
        return majority;
    }
}


Other Posts You May Like
Please leave a comment below if you like this post or found some errors, it will help me to improve my content.
By

Comments

Post a Comment

Popular Posts from this Blog

N-th Tribonacci Number Solution - The Coding Shala

Home >> Programming >> N-th Tribonacci Number  Hey there, welcome back to another post. In this post, we will learn how to solve the N-th Tribonacci Number problem and will implement its solution in Java. N-th Tribonacci Number Problem Statement The Tribonacci sequence Tn is defined as follows: T0 = 0, T1 = 1, T2 = 1, and Tn+3 = Tn + Tn+1 + Tn+2 for n >= 0. Given n, return the value of Tn.  Example 1:  Input: n = 4 Output: 4 Explanation: T_3 = 0 + 1 + 1 = 2 T_4 = 1 + 1 + 2 = 4 N-th Tribonacci Number Java Solution using Bottom-Up DP This problem is similar to the Fibonacci series. We can solve it using the Bottom-Up approach of dynamic programming. Time Complexity: O(n) Space Complexity: O(n) The space complexity can be reduced to O(1) by using variables to store the previous three values instead of using an array. Java Program:  class Solution { public int tribonacci( int n) { if (n == 0) return 0; if (n == 1 || n == 2
Read more

Shell Script to find sum, product and average of given numbers - The Coding Shala

Home >> Scripting >> Sum, product and average Shell Script to find the sum, product, and the average of given numbers Read four integer numbers from the user and find the sum, product, and average of these four numbers? Code:  #! / bin / bash echo "enter four integers" read a b c d sum =$(echo "$a + $b + $c + $d" | bc - l) average=$(echo "$sum / 4" | bc - l) product=$(echo "$a * $b * $c * $d" | bc - l) echo "sum = $sum" echo "Average = $average" echo "Product = $product" Other Posts You May Like Shell script to print sum of the digits of a number Shell Script to print number in descending order Shell script to find out biggest number from three numbers Shell script to find out factorial of a number Shell Script to create a simple calculator Please leave a comment below if you like this post or found some error, it will help me to improve my content.
Read more

Find Second Smallest Element in the Array - The Coding Shala

Home >> Programming >> Find Second Smallest Element in the Array  Hey there, welcome back to another post. In this post, we will learn how to find the second smallest number in the array in Java. Find Second Smallest Element in the Array Problem Statement You have given an integer array, return the second smallest element from the array if exists else return no second smallest element exists. Example 1:  Input: [1, 4, 2, 7, 90, -1, -4] Output: -1 Find Second Smallest Element in the Array Solution using Single Iteration Approach By using the below steps we can find the second smallest element in the array by using a single iteration: Initialize two variables first and second for smallest and second smallest numbers and the initial value will be Integer.MAX_VALUE. Traverse the array and check if the current element is smaller than the smallest element then update both first and second. If the current element is between first and second then only update the seco
Read more

New Year Chaos Solution - The Coding Shala

Home >> Programming Questions >> New Year Chaos New Year Chaos Problem Solution In this post, you will learn how to solve New Year Chaos Problem and implement its solution in Java. Problem:   It's New Year's Day and everyone's in line for the Wonderland rollercoaster ride! There are a number of people queued up, and each person wears a sticker indicating their initial position in the queue. Initial positions increment from at the front of the line to at the back.  Any person in the queue can bribe the person directly in front of them to swap positions. If two people swap positions, they still wear the same sticker denoting their original places in line. One person can bribe at most two others.  For Example, if n=8 and Person 5 bribes Person 4, the queue will look like this: 1,2,3,5,4,6,7,8. Fascinated by this chaotic queue, you decide you must know the minimum number of bribes that took place to get the queue into its current state. Input:
Read more

Shell Script to Create a Simple Calculator - The Coding Shala

Home >> Scripting >> simple calculator Shell Script to Create a Simple Calculator Write a shell script to create a simple calculator using a switch-case statement? Code:  #! / bin / bash echo "simple calculator" sum = 0 i = "y" echo "enter first number" read n1 echo "enter second number" read n2 while [ $ i = "y" ] do echo "1.Addition" echo "2.Subtraction" echo "3.Multiplication" echo "4.Division" echo "Enter choice" read ch case $ch in 1 ) sum =$(echo " $n1 + $n2" | bc - l) echo "Addition is =" $ sum ;; 2 ) sum =$(echo "$n1 - $n2" | bc - l) echo "Sub is =" $ sum ;; 3 ) sum =$(echo "$n1 * $n2" | bc - l) echo "Mul is =" $ sum ;; 4 ) sum =$(echo "$n1 / $n2" | bc - l) echo "div is =" $ sum ;; * )echo "invalid choice" esac echo "Do y
Read more