Boyer-Moore majority vote algorithm second iteration

Question

There's a problem in one of my textbooks that goes as follows.

You are given the results of a presidential election. Each ballot is presented one by one, and on each ballot the name of a candindate is written(Let's assume candidates name's are represented by numbers). Before announcement of the result, the total number of candidates and the number of people who voted, are unknown.All valid ballots are presented on by one as input, and this process repeats 2 times total. We only have 2 simple varibles we can use for the whole process. You have to design an algorithm which can decide if there is a candidate that has gathered the majority of the votes(meaning more than 50%) of the people who voted, or not. If such a candidate exists, print the candidates name otherwise print "blah blah blah"

Now what first got into my mind, is to use the Boyer-Moore majority algorithm and keep updating the majority and the counter variables as soon as the next result comes in. In case i haven't made that clear, the results aren't stored in an array or anywhere else. You get informed of one ballot, then you calculate(and this goes on until all the ballots have been used, meaning i don't have access to any previous information). Whether this information is stored in array or not, i know i can still run the first iteration of this algorithm to get a "possible" majority result, since the algorithm always produces one. My problem lies in the second iteration.I see the results one more time one by one. How am i supposed to verify if my original result is indeed the majority or not? Is there any other way i can get around it with only 2 variables?

Answer 1

I assume that we are allowed to use loops and loop variable to iterate over a list.

Let's assume that the election information are stored in votes. It contains the candidate number which the people have voted. We will think each of the candidate as winner and store each candidate number as the winner in each iteration. If we can find any candidate number more or equal to 50% of the number of votes, we can infer the candidate is the winner. Thus we can only use two variables count and winner to get the winner's name.

def get_winner(votes):

    count = None
    winner = None

    for i in range(len(votes)):
        winner = votes[i]
        count = 0
        for j in range(i, len(votes)):
            if votes[i] == votes[j]:
                count += 1
        if count >= len(votes)*0.5:
            return winner
    return "blah blah blah"

if __name__ == "__main__":
    votes = [1, 3, 3, 3, 3, 3, 3, 2, 4, 1, 8]
    print(get_winner(votes))

Output:

3

Answer 2

You can do a first iteration and keep track of the votes in a single variable. Now the value of this variable "may be" a majority. Now do a second iteration and count the number of occurrences in a second variable of the majority candidate indicated by the first iteration. This is for verifying if the candidate indicated by the first pass is indeed in majority. Overall you just need 2 variables and 2 iterations. By the way, here's a good introduction to the Boyer Moore's voting algorithm - https://satyadeepmaheshwari.medium.com/boyer-moore-voting-algorithm-in-plain-english-4a343fb4c6a1