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:



  1. The winner has to record at least X% votes (a unique leader is guaranteed to exist, as indicated by the vortessence)

  2. 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?

Comments (8)

  1. Sushant Bhatia says:

    Am I missing something here.

    I can use vortessence to get the precise time when a unique leader first appears and use that info to seek through the log file for that precise time (assuming all entries are going to differ in time) and then look up on that line the name of the person who won.

    So minimal log passes is 1.

    On the right track or completely off? 🙂

  2. Adi Oltean says:

    Notes:

    – The log doesn’t contain timestamps.

    – The log contains votes performed only after a unique leader appears.

  3. Adi Oltean says:

    Allright – I will post the solution next week! (if there are no other comments)

  4. Lailin Chen says:

    Well, Since we already knew there is one and only one who has more votes than any others, we can find him by letting the votes "fight" each other:

    Picked the first one, say X1, count 1 for X1, then move on,  if X1 repeats, add count to X1.

    When X1 doesn’t repeat, reduce the count by one, if it reaches 0, picked up the current one (say X2), and do the some counting to X2.  

    Keep doing this until the end. The last one left with a counting bigger than 0 is the leader:

    X3  X1  X1  X2  X1  X3  X3  X3  X4

       ^

    X3, 1

    X3  X1  X1  X2  X1  X3  X3  X3  X4

             ^

           X3, 0

    X3  X1  X1  X2  X1  X3  X3  X3  X4

                   ^

                X1, 1

    X3  X1  X1  X2  X1  X3  X3  X3  X4

                         ^

                       X1, 0

    X3  X1  X1  X2  X1  X3  X3  X3  X4

                               ^

                              X1, 1

    X3  X1  X1  X2  X1  X3  X3  X3  X4

                                     ^

                                   X1, 0

    X3  X1  X1  X2  X1  X3  X3  X3  X4

                                           ^

                                        X3, 1

    X3  X1  X1  X2  X1  X3  X3  X3  X4

                                                 ^

                                               X3, 2

    X3  X1  X1  X2  X1  X3  X3  X3  X4

                                                        ^

                                                      X3, 1

    So X3 is the winner.

    The condition would be the percentage X% >= 50%

  5. Adi Oltean says:

    Cool – Lailin – you got the right solution for X > 50% !

    Actually the algorithm above works _only_ if X > 50%.

    How about the case when X <= 50% ?

  6. Antimail says:

    I think that the problem stated in one of my earlier posts is one of the most fascinating puzzles I came

  7. I think that the problem stated in one of my earlier posts is one of the most fascinating puzzles I came