Share via

think you're good at puzzles? try this one.

  • Article

I ran
across this puzzle a little while ago. I’m still working on it –
now you can too:

You
have a port that you are reading numbers from. You know that there is one number that
is generated in more than half of the cases. You keep reading numbers arbitrarily
long until you are given a command to stop. When you stop you have to return the number
that has occurred in more than half of the cases.

(Hint: you don’t
have enough memory to store all the numbers)

Comments

  • Anonymous
    December 08, 2003
    read the first number - that's it
  • Anonymous
    December 09, 2003
    neil: that doesn't work, because you don't get to decide when to stop. "you are given a command to stop."
  • Anonymous
    December 11, 2003
    I solved it.int n = readPort()int nplusone = readPort()HashMap list = new HashMap()while(not told to stop){ if (nplusone == n) { list.put(n, list.get(n) ? list.get(n)+1:1) } n = nplusone nplusone=readPort()}int count=0;int number;foreach(key in list){ if(list.get(key) > count) { count = list.get(key) number = key }}return number
  • Anonymous
    December 11, 2003
    The comment has been removed