Puzzle: Xen voting algorithm
There is a huge amount of aliens living on the Xen planet who want to elect their new leader (since their previous leader died a while back). They want to switch to a very democratic voting process, through the help of a very special communication field called the “vortessence”.
One interesting property of voting through vortessence is that it can tell them whether there is a certain unique leader which is guaranteed to meet a certain percentage of votes X% (which is a number chosen ahead of time and can be considered constant in this discussion). But the vortessence cannot be used to tell who is actually the winning leader.
So these aliens will also use the help of a computer to record the voting. The rules are simple:
- The winner has to record at least X% votes (a unique leader is guaranteed to exist, as indicated by the vortessence)
- Each alien votes exactly once, by indicating the name of the proposed leader.
After the voting season, the votes are recorded in a very large unsorted log file, containing the names of the voted aliens. Now, since there are a lot of aliens, they need to use an algorithm to figure out the leader, running in O(1) in space and O(N) in time (name comparisons can be considered constant).
In what conditions is this problem solvable, and if yes, what is the minimal number of log passes?