Guess a Number from 1 to 1000 with Yes or No Questions
Algorithms question on binary search, which halves the interval at each question
The riddle
I am thinking of a whole number between 1 and 1000. You may ask me questions, to which I answer only yes or no. How many yes-or-no questions are enough, in the worst case, to guess this number for sure?
Need a hint?
Do not test the numbers one by one: choose each question so that it eliminates half of the remaining possibilities.
Show the answer and the solution
Answer: 10 questions: each answer halves the number of possibilities, and 2 to the power 10 is 1024, more than 1000.
The reasoning
Each yes-or-no question splits the remaining possibilities into two groups, for example by asking whether the number is greater than 500. Whatever the answer, we keep one half of the interval and repeat the process on that new half. After k questions, at most about 1000 divided by 2 to the power k possibilities remain. With 9 questions, we can only distinguish 2 to the power 9, or 512 cases, which is not enough for 1000 numbers. With 10 questions, we distinguish 2 to the power 10, or 1024 cases, which is enough. The answer is therefore 10 questions in the worst case. This principle is that of binary search, with complexity O(log n).
What next?
Reasoning improves like memory: by practising often. Next, test yourself on our general knowledge quizzes.