Edit Question - KnowledgeHub

Title Body

As I was reading this ( Find the most common entry in an array ), the Boyer and Moore's Linear Time Voting Algorithm was suggested. If you follow the link to the site, there is a step by step explanation of how the algorithm works. For the given sequence, AAACCBBCCCBCC it presents the right solution. When we move the pointer forward over an element e: If the counter is 0, we set the current candidate to e and we set the counter to 1. If the counter is not 0, we increment or decrement the counter according to whether e is the current candidate. When we are done, the current candidate is the majority element, if there is a majority. If I use this algorithm on a piece of paper with AAACCBB as input, the suggested candidate would become B what is obviously wrong. As I see it, there are two possibilities The authors have never tried their algorithm on anything else than AAACCBBCCCBCC , are completely incompetent and should be fired on the spot (doubtfull) . I am clearly missing something , must get banned from Stackoverflow and never be allowed again to touch anything involving logic. Note: Here is a a C++ implementation of the algorithm from Niek Sanders. I believe he correctly implemented the idea and as such it has the same problem (or doesn't it?).

Tags (comma-separated) Cancel