Tricky Microsoft interview question that Reddit got so wrong

Here is the question: http://mindcipher.net/puzzle/166-microsoft-interview-question-count-it-out

And here is the Reddit thread: http://www.reddit.com/r/programming/comments/95hl2/tricky_microsoft_interview_question/

The obvious solution I see is O(N) in both space and time: just go through the numbers and mark the ones you see in an array. The one that is left unmarked is the missing number.

Reddit commentors propose O(nlogn) complex solutions. Modified quicksort ? Map reduce ? Oh common.