Program to Find majority element (Boyer–Moore Majority Vote Algorithm)

Python Program to Find majority element (Boyer–Moore Majority Vote Algorithm)

Don’t miss the chance of Java programs examples with output pdf free download as it is very essential for all beginners to experienced programmers for cracking the interviews.

Given a list, the task is to find the majority element of the given list.

Majority Element:

A majority element appears more than n/2 times, where n is the size of the array.

Boyer–Moore Majority Vote Algorithm History and Introduction:

The Boyer–Moore majority vote algorithm uses linear time and constant space to determine the majority of a series of elements. It is named after Robert S. Boyer and J Strother Moore, who published it in 1981, and is an example of a streaming algorithm.

In its most basic version, the algorithm looks for a majority element, which is an element that appears frequently for more than half of the items in the input. A version of the procedure that performs a second pass through the data can be used to confirm that the element found in the first pass is truly a majority.

If no second pass is conducted and there is no majority, the algorithm will not identify that there is no majority. In the absence of a rigorous majority, the returned element can be random; it is not guaranteed to be the most frequently occurring element (the mode of the sequence). A streaming method cannot discover the most frequent element in less than linear space for sequences with a limited number of repetitions.

Program to Find majority element (Boyer–Moore Majority Vote Algorithm)

Below is the full approach for finding the majority element present in the given array using Boyer-Moore Majority Vote Algorithm.

1)Algorithm:

The algorithm takes up O(1) more space and runs in O(N) time. It takes exactly two traverses across the input list. It’s also pretty straightforward to implement, however understanding how it works is a little more difficult.

We generate a single candidate value in the first traversal, which is the majority value if there is one. To confirm, the second pass simply counts the frequency of that value. The first pass is the most interesting.

We require two values in the first pass:

A candidate value, which can be set to any value at first.
A count, which is originally set to 0.
We begin by looking at the count value for each entry in our input list. If the count is equal to zero, the candidate is set to the value at the current element. Then, compare the value of the element to the current candidate value. If they are the same, we add one to the count. If they vary, we reduce the count by one.
If a majority value exists at the end of all inputs, the candidate will be the majority value. A second O(N) traversal can be used to ensure that the candidate is the majority element.

 Initialize an element ele and a counter in = 0

for each element x of the input sequence:
if in = 0, then
assign ele = x and in = 1
else
if ele = x, then assign in = in + 1
else
assign in = in – 1
return ele

2)Implementation(Static Input)

Give the list as static input and store it in a variable.

Pass the given list to the majoElement function which accepts the given list as an argument and implement the Boyer–Moore majority vote algorithm.

It returns the majority element.

Each element of the sequence is processed one at a time by the algorithm. When working with an element x.
If the counter is zero, set the current candidate to x, and the counter to one.
If the counter is not zero, it should be incremented or decremented depending on whether x is a current contender.
If the sequence has a majority at the end of this phase, it will be the element stored by the algorithm. If there is no majority element, the algorithm will fail to detect it and may output the incorrect element. In other words, when the majority element is present in the input, the Boyer–Moore majority vote algorithm delivers proper results.

Below is the implementation:

# Function to find the majority element present in a given list
def majoElement(given_list):
    # majo stores the majority element (if present in the given list)
    majo = -1
    # initializing counter index with 0
    ind = 0
    # do for each element `A[j]` in the list
    for j in range(len(given_list)):
        # check if the counter index is zero or not.
        if ind == 0:
            # set the current candidate of the given list to givenlist[j]
            majo = given_list[j]
            # change the counter index to 1.
            ind = 1
        # Otherwise, if givenlist[j] is a current candidate, increment the counter.
        elif majo == given_list[j]:
            ind = ind + 1
        # Otherwise, if givenlist[j] is a current candidate, decrement the counter.
        else:
            ind = ind - 1
    # return the majority element
    return majo


# Driver Code
# Give the list as static input and store it in a variable.
given_list = [4, 11, 13, 9, 11, 11, 11, 3, 15, 28, 11, 11, 11, 11]
# Pass the given list to the majoElement function which accepts
# the given list as an argument
# and implement the Boyer–Moore majority vote algorithm.

print("The majority element present in the givenlist",
      given_list, '=', majoElement(given_list))

Output:

The majority element present in the givenlist [4, 11, 13, 9, 11, 11, 11, 3, 15, 28, 11, 11, 11, 11] = 11

3)Implementation(User Input)

i)Integer List

Give the Integer list as user input using map(), int, split(), and list() functions.

store it in a variable.

Pass the given list to the majoElement function which accepts the given list as an argument and implement the Boyer–Moore majority vote algorithm.

It returns the majority element.

Each element of the sequence is processed one at a time by the algorithm. When working with an element x.
If the counter is zero, set the current candidate to x, and the counter to one.
If the counter is not zero, it should be incremented or decremented depending on whether x is a current contender.
If the sequence has a majority at the end of this phase, it will be the element stored by the algorithm. If there is no majority element, the algorithm will fail to detect it and may output the incorrect element. In other words, when the majority element is present in the input, the Boyer–Moore majority vote algorithm delivers proper results.

Below is the implementation:

# Function to find the majority element present in a given list
def majoElement(given_list):
    # majo stores the majority element (if present in the given list)
    majo = -1
    # initializing counter index with 0
    ind = 0
    # do for each element `A[j]` in the list
    for j in range(len(given_list)):
        # check if the counter index is zero or not.
        if ind == 0:
            # set the current candidate of the given list to givenlist[j]
            majo = given_list[j]
            # change the counter index to 1.
            ind = 1
        # Otherwise, if givenlist[j] is a current candidate, increment the counter.
        elif majo == given_list[j]:
            ind = ind + 1
        # Otherwise, if givenlist[j] is a current candidate, decrement the counter.
        else:
            ind = ind - 1
    # return the majority element
    return majo


# Driver Code
# Give the list as user input using map(), int, split(), and list() functions.

# store it in a variable.
given_list = list(map(int,
    input('Enter some random elements of the given list separated by spaces = ').split()))
# Pass the given list to the majoElement function which accepts
# the given list as an argument
# and implement the Boyer–Moore majority vote algorithm.

print("The majority element present in the givenlist",
      given_list, '=', majoElement(given_list))

Output:

Enter some random elements of the given list separated by spaces = 8 12 45 96 3 7 7 1 5 7 7 7 5
The majority element present in the givenlist [8, 12, 45, 96, 3, 7, 7, 1, 5, 7, 7, 7, 5] = 7

ii)String List

Give the string list as user input using split(), and list() functions.

store it in a variable.

Below is the implementation:

# Function to find the majority element present in a given list
def majoElement(given_list):
    # majo stores the majority element (if present in the given list)
    majo = -1
    # initializing counter index with 0
    ind = 0
    # do for each element `A[j]` in the list
    for j in range(len(given_list)):
        # check if the counter index is zero or not.
        if ind == 0:
            # set the current candidate of the given list to givenlist[j]
            majo = given_list[j]
            # change the counter index to 1.
            ind = 1
        # Otherwise, if givenlist[j] is a current candidate, increment the counter.
        elif majo == given_list[j]:
            ind = ind + 1
        # Otherwise, if givenlist[j] is a current candidate, decrement the counter.
        else:
            ind = ind - 1
    # return the majority element
    return majo


# Driver Code
# Give the string list as user input using split(), and list() functions.

# store it in a variable.
given_list = list(input('Enter some random elements of the given list separated by spaces = ').split())
# Pass the given list to the majoElement function which accepts
# the given list as an argument
# and implement the Boyer–Moore majority vote algorithm.

print("The majority element present in the givenlist",
      given_list, '=', majoElement(given_list))

Output:

Enter some random elements of the given list separated by spaces = hello this is btechgeeks is is is si is is
The majority element present in the givenlist ['hello', 'this', 'is', 'btechgeeks', 'is', 'is', 'is', 'si', 'is', 'is'] = is

Related Programs: