5

A majority voting algorithm decides which element of a sequence is in the majority, provided there is such an element. Here is the most frequently-cited link that I found when I was trying to understand it.

http://www.cs.utexas.edu/~moore/best-ideas/mjrty/index.html

Besides, we have here a link that discusses the problem:

How to find the element of an array that is repeated at least N/2 times?

The problem is that the answer marked as correct is WRONG. Note that the question actually allows the input to have exactly N / 2 copies of a single element (not necessarily more than N / 2 as usually assumed in majority element detection algorithms).

I copied the code and tried it with inputs like [1, 2, 3, 2] and [1, 2, 3, 2, 6, 2] (producing results of 3 and 6). This actually applies as well to the algorithm cited above (which returns "No Majority Element!"). The problem is this: Whenever there's an alternation between the majority element and anything else, the last element in the array that's not the majority element is chosen. Please correct my wrong thoughts if any, and tell me about how to avoid it in the implementation.

Community
  • 1
  • 1
OmarOthman
  • 1,718
  • 2
  • 19
  • 36

2 Answers2

11

The algorithm is correct: there is no majority element in your examples. An element is in the majority only if it is more than 50% of the values.

If you wish to detect the case where the most frequent element has a count of N/2, then I don't see any way to do it in one pass and O(1) space. My best attempt is:

  • Run the same algorithm as before, but remember the previous candidate as well.
  • If you switched at the last element, then the correct answer is either your current or your previous candidate.
  • Run another pass, counting the number of each, and compare them.
sverre
  • 6,768
  • 2
  • 27
  • 35
  • +1 for the quick and intelligent solution. I've tried all possible corner cases and your algorithm works fine. Thank you... – OmarOthman Oct 25 '11 at 19:28
  • Please could you illustrate this with one of the given examples of `[1, 2, 3, 2]` or `[1, 2, 3, 2, 6, 2]` (e.g. [like I did for some other examples here](http://stackoverflow.com/questions/4280450/linear-time-majority-algorithm/4282037#4282037))? The candidate is *never* set to the correct answer of 2 in either case, so I'm not sure how remembering an additional candidate helps. (Maybe I'm just being confused by the way you've worded this - a worked example would really help.) – Matthew Slattery Oct 27 '11 at 20:17
  • 1
    [@MatthewSlattery] You're completely right, sorry not to explain this in more detail (I did it on paper actually). The point is that: Fixing this [code](http://stackoverflow.com/questions/3740371/finding-the-max-repeated-element-in-an-array/3740423#3740423) by settling on the next candidate *instantly* when the counter reaches 0. So: [1] 1, 1 [2] 2, 1 [3] 3, 1 [2] 2, 1 [6] 6, 1 [2] 2, 1. Counting the number of occurrences of 2 and 6 (or 2 and 3 in the other example) actually reveals that 2 is the correct answer. Please tell me your thoughts about that... and thanks for your care to reply :-). – OmarOthman Oct 31 '11 at 12:42
  • Can you please explain me how this logic works if the given input is [1, 1, 1, 2, 2, 3, 3, 4, 4]? – user1010 Sep 18 '12 at 14:36
3

OK, so I think I now understand what @sverre is getting at. Here's a proof that it works:

  • If exactly N/2 elements are the same value (call this value m), N must be even.

  • Split these elements into two parts: the first N-1 elements, and the last element. Given that a total of N/2 elements are equal to m, then either:

    1. the last element is not m, in which case N/2 of the first N-1 elements are equal to m, and therefore the first N-1 elements have a strict majority m; or
    2. the last element is m, in which case (N/2)-1 of the first N-1 elements are equal to m, and therefore the first N-1 elements do not have a strict majority.

  • In case 1), m is the candidate just before processing the last element (because, at that point, we've just processed N-1 elements, and we know that a strict majority does exist in this case, so that candidate must be the correct answer).

  • In case 2), m is the last element itself. (This is the part which was confusing me: in the usual implementation of the algorithm, this would not necessarily become the candidate as it was processed.)

So:

  • For a strict majority (> N/2 elements the same), the answer (if it exists) is the final candidate.

  • For a non-strict majority (>= N/2 elements the same), the answer (if it exists) is one of:

    1. the final candidate; or
    2. the candidate just before processing the last element; or
    3. the last element.
Matthew Slattery
  • 45,290
  • 8
  • 103
  • 119