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

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

LeetCode - Bulb Switcher Solution - The Coding Shala

Image
Home >> LeetCode >> Bulb Switcher LeetCode - Bulb Switcher Solution In this post, we will discuss LeetCode's Bulb Switcher Problem and its solution in Java. There are n bulbs that are initially off. You first turn on all the bulbs. Then, you turn off every second bulb. On the third round, you toggle every third bulb (turning on if it's off or turning off if it's on). For the i-th round, you toggle every i bulb. For the n-th round, you only toggle the last bulb. Find how many bulbs are on after n rounds. Example: Input: 3 Output: 1 Explanation: At first, the three bulbs are [off, off, off]. After the first round, the three bulbs are [on, on, on]. After the second round, the three bulbs are [on, off, on]. After the third round, the three bulbs are [on, off, off].  So you should return 1 because there is only one bulb is on. Practice this problem on LeetCode(Click Here). Java Solution of Bulb Switcher Problem Let's
Read more

Anti Diagonals - The Coding Shala

Image
Home >> Interview Questions >> Anti Diagonals Anti Diagonals Java Solution Give an N*N square matrix, return an array of its anti-diagonals. Look at the example for more details. Example: Input: 1 2 3 7 8 9 4 5 6 Return the following : [ [1], [2, 4], [3, 5, 7], [6, 8], [9] ] Input : 1 2 3 4 Return the following : [ [1], [2, 3], [4] ] Anti Diagonals Java Solution 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 public class Solution { public ArrayList < ArrayList < Integer >> diagonal ( ArrayList < ArrayList < Integer >> A ) { ArrayList < ArrayList < Integer >> ans = new ArrayList < ArrayList < Integer >>(); int N = A . size (); int i = N - 1 ; while ( i >= 0 ){ ArrayList < Integer > tmp = new ArrayList < Integer >();
Read more

Sorting the Sentence LeetCode Solution - The Coding Shala

Home >> LeetCode >> Sorting the Sentence  In this post, we will learn how to solve LeetCode's Sorting the Sentence Problem and will implement its solution in Java. Sorting the Sentence Problem A sentence is a list of words that are separated by a single space with no leading or trailing spaces. Each word consists of lowercase and uppercase English letters. A sentence can be shuffled by appending the 1-indexed word position to each word then rearranging the words in the sentence. For example, the sentence "This is a sentence" can be shuffled as "sentence4 a3 is2 This1" or "is2 sentence4 This1 a3". Given a shuffled sentence s containing no more than 9 words, reconstruct and return the original sentence. Example 1: Input: s = "is2 sentence4 This1 a3" Output: "This is a sentence" Explanation: Sort the words in s to their original positions "This1 is2 a3 sentence4", then remove the numbers. Example 2: Input:
Read more

Java Method Overloading - The Coding Shala

Image
Home >> Learn Java >> Java Method Overloading Java Method Overloading Java class can have more than one method with the same name but different in parameters, known as Method Overloading. Question: What is the use of method overloading? Answer:  Suppose we want to perform some operation like an addition but addition can be performed between two numbers, three numbers or two floats or more. So instead of using different methods, we use the same name of the method with different parameters. This can increase the readability of the program. Method overloading can be achieved by changing numbers of arguments or by changing the data types. Example of Method Overloading in Java The following example explains Method Overloading: //Method Overloading example class Addition { public int add ( int a , int b ){ return a + b ; } public int add ( int a , int b , int c ){ return a + b + c ; }
Read more