|
Spoiler alert: The following riddle builds on ideas that
were discussed in the riddles of December 2008 through February 2009 and
their solutions. If you still mean to tackle those other riddles (and if you
haven't yet, I recommend that you do; they are some of my favourite
Using your Head is Permitted riddles), then you may want to hold on before you
continue to this one. On the solution page I will assume familiarity
with those older riddles.
Zhang Kaiyuan sent in the following wonderful question (Thanks Zhang!): Given the usual complexity assumptions, can you sort n real numbers in O(n) time? As usual: prove your answer. |
List of solvers:Lin Jin (8 September 00:01)Uoti Urpala (9 September 12:42) Oscar Volpatti (29 September 22:54) |
Elegant and original solutions can be submitted to the puzzlemaster at riddles
brand.scso.com.
Names of solvers will be posted on this page. Notify if you don't want
your name to be mentioned.
The solution will be published at the end of the month.
Enjoy!