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?