The fact that the sequence A, A, A, B, B, C output C as the leader is a bit underwhelming.
I find the (n/2 + 1) majority limitation a little harsh, but indeed it's an elegant solution to a very common problem.
It seems pretty rare that you'd have a large data set and know that there is a majority without knowing what that majority is. But if that was the case, then this would be the optimal algorithm.
It was more important when older computers had different restrictions:
Note that the algorithm fetches the elements of A in linear order. Thus, the algorithm can be used efficiently when the number of votes is so large that they must be read from magnetic tape.
For further actions, you may consider blocking this person and/or reporting abuse
We're a place where coders share, stay up-to-date and grow their careers.
Took me quite some time to comprehend. Good one though!
But I have a couple genuine questions.
Is this algorithm practically applicable? If we needed to implement a voting system, would we use this algorithm?
And, will this behavior reflect in real life where we have huge number of elements?
The fact that the sequence
A, A, A, B, B, Coutput C as the leader is a bit underwhelming.I find the
(n/2 + 1)majority limitation a little harsh, but indeed it's an elegant solution to a very common problem.It seems pretty rare that you'd have a large data set and know that there is a majority without knowing what that majority is. But if that was the case, then this would be the optimal algorithm.
It was more important when older computers had different restrictions: