Majority vote efficient implementation

Question

election time !

Each candidate is represented by a letter a..z. You need to tell if one candidate get the majority of the votes and wins, or not.

Make a program taking a string as input and displays the letter of the winning candidate or "" if nobody wins a majority.

Bonus: do it in one pass, dont use builtin find/count functions and limited memory use in the main loop.

aaaeecacffggaa => a
iibcidieei => "" (i gets just 50% of the votes, you need at least 50%+1 vote to have a majority)
abcde => ""

Answer 1

Here is a Java solution I think it's very efficient. This solution uses a map for counting all votes while iterating ones through the given Input String. Then it iterates through the map to analize it and return a result.

If you have an input String of length n and m different candidates, this solution needs n+m steps to return a solution. The memory used is the used map with m entries.

Solution: https://code.sololearn.com/cHu3H6de9t99/?ref=app

Btw, your example is wrong:

aaaeecacffgga --> 5x 'a', 2x 'c', 2x 'e', 2x 'f', 2x 'g'
so 'a' has 38.5 % and it's not an absolute majority which you want to get as a result. Which is implied by your second example about the 'i'.

Here is a working example: aaabbac --> returns 'a'

Answer 2

In one pass:
https://code.sololearn.com/ck25t9EwQAJO/?ref=app

Answer 3

Thank you Andreas.
It has now been modified for the winner with non-absolute majority. In case we have an equal score - there is no winner.
In one pass 😊

Answer 4

https://code.sololearn.com/c1v090n3lBx5/?ref=app

Answer 5

Nice modification to my solution. An integration of the analysis into the counter phase. Well done. Didn't see it while programming my one. But this is just possible for absolute majority. So for a special case. So it's great for this challenge.

Answer 6

well done. @Luka

Answer 7

I would like to see a solution with n steps // For others, n represents the length of the input String//
And thanks for your quick view on the code.

Answer 8

Oh I would appreciate to see the code to this. It seems like a type of predictive algorithm by analysing while counting through the String, isn't it?

Answer 9

Nice solution.

Answer 10

good one. note that n is possible though.

Answer 11

@andreas the n steps, 2 variables no array solution only works when there is a winner (if there is not, it returns a letter without telling there no winner)

Answer 12

If you want to be sure you are a real winner you need a second pass. Since the code is very simple this should be faster than any other solution