Prisoners and Poison

A bad king has a cellar of 1000 bottles of delightful and very expensive wine.

A neighboring queen plots to kill the bad king and sends a servant to poison the wine.
Fortunately (or say unfortunately) the bad king’s guards catch the servant after he has only poisoned one bottle.
Alas, the guards don’t know which bottle but know that the poison is so strong that even if diluted 100,000 times it would still kill the king.

Furthermore, it takes one month to have an effect. The bad king decides he will get some of the prisoners in his vast dungeons to drink the wine. Being a clever bad king he knows he needs to murder as less prisoners as possible – believing he can fob off such a low death rate – and will still be able to drink the rest of the wine (999 bottles) at his anniversary party in 5 weeks time.

In the worst case, what is the minimum number of prisoner he would have to kill in order to find out the poisoned bottle? Do note that the king wants to minimize the number of prisoners involved in the experiment. He might decide to kill every prisoner involved in the experiment if he feels that they may tell the world about his evil plans.

Answer is a integer. Just put the number without any decimal places if its an integer. If the answer is Infinity, output Infinity.

Feel free to get in touch with us if you have any questions

  • Solution Approach
  • Complete Solution
2122 successful submissions.
Asked In:
  • Amazon
Click here to jump start your coding interview preparation