Given the numbers 1 to 1000, what is the minimum number of guesses needed to find a specific number if you are given the hint ‘higher’ or ‘lower’ for each guess you make?

This may be considered a trick question, since it’s deceptively easy. Read the question carefully and you’ll note that the question asks for the ‘minimum’ number of guesses. Think about it – someone can guess the right question on their first try right?

So, the answer here would be ‘1’, since it would take only one correct guess to find a specific number.

Finding the maximum number of guesses

But, what if we wanted to find the maximum number of guesses?




Well, think about this one. What if the number that you have to guess is ‘1’ and you start guessing from 1,000? Then, if the person who knows the number keeps saying lower, then you would guess 999,998,997…6,5,4,3,2, and finally until you get to 1.

The maximum number of guesses

This means that the maximum number of guesses is 999.

But, you must be thinking that’s a stupid answer – because no one would take that approach to guessing unless they were really foolish.

Using Binary Search to find a number from 1 to 1,000

The approach most programmers would take is by starting your guess in the middle of the set of numbers, and then continuing to divide the set of numbers in half with each guess. This approach to guessing (or “searching” for the number) is known as a binary search to most software engineers, and it is also known as a half-interval search. Let’s go through an example of how the binary search would work so that you can further understand the approach to solving this problem.

An example of using the binary search

So, let’s say the number you were trying to guess is a ‘1’. Then, you would start from the middle of 1,000 – which is 500. The person giving you hints would keep saying lower – and you would end up with something like this sequence of numbers to represent your guesses:

500, 250, 125, 63, 32, 16, 8, 4, 2, 1




Counting the number of guesses above would give you 10, which is our answer to the maximum number of guesses to find a number between 1 and 1000. In a binary search, if you take the log base 2 of the number of numbers (in this case, 1000), that would also give you the maximum number of guesses to find the correct number. So, if we take the log base 2 of 1,000 it would give us 9.965. Since you can’t possibly have a fraction of a guess, the result of log base 2 of 1000 should be rounded up to a whole number, which is 10, and the answer.

Hiring? Job Hunting? Post a JOB or your RESUME on our JOB BOARD >>

Subscribe to our newsletter for more free interview questions.

  • Russell Smith

    It is 10. It could be 9, for the same reason it could be 1, but disregarding lucky guesses, the minimum to get it every time is 10. Your logic is sound, but you didn’t consider that the answer “higher” will land you on the side with more numbers (if you use 14 and answer 7; then there are 7 numbers higher and only 6 lower). It is this scenario that requires the extra guess.

  • sandywho

    10 is the worst case scenario

  • IndrajiT

    What if I took 500???

  • Nora

    I have a question: say at the stage when we have 125 numbers left, the guesser would pick a number, which reduces the amount of numbers yet to be guessed to be 124. Divide this by 2 and you get 62, then 31, round it down (the guesser picks 1 number) to 30, you get 15, round down to 14, then we get 7, round to 6, we get 3, then round to 2, and we only get one chance left to guess. That makes it 9 guesses in total. Can it be 9 rather than 10? Is there any problem in this approach? I haven’t written any program to test this, just trying to think logically.

  • Alexandre Saccol

    lol

  • kaydenlol3

    you can guess the number

  • Dumbfound

    Unless they’d be really stupid or something.

  • ManticoreInPrison

    Actually maximum number is infinite. Because someone may keep picking the same wrong guess and never get the right one 🙂