Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Table of contents
1.
Introduction
2.
Problem Statement
3.
Solution
4.
Frequently Asked Questions
4.1.
Can we solve the puzzle for 1022 bottles? Will the answer change?
4.2.
What will be the best-case scenario( how many minimum prisoners will die)?
4.3.
Why should I practice puzzles?
4.4.
Do MNCs ask puzzles in the interview of IT companies?
4.5.
From where can I practice more such puzzles?
5.
Conclusion
Last Updated: Mar 27, 2024

Prisoners and Poison

Author Apoorv Dixit
1 upvote
Master Python: Predicting weather forecasts
Speaker
Ashwin Goyal
Product Manager @
Interview Puzzles

Introduction

Puzzles are critical thinking problems that test a person's lateral thinking and problem-solving skills, similar to brain teasers. These types of puzzle questions are commonly used by interviewers to assess a potential employee's ability to solve complex problems using strategies and higher-order thinking to determine their fit for the company.

In this article, we will be discussing a famous puzzle- ‘Prisoners and Poison.’

Problem Statement

An evil king has a cellar stocked with 1000 bottles of delectable and pricey wine.

A neighboring queen plots to assassinate the bad king by poisoning wine. She sends a ninja to poison the wine. The ninja gets caught by the bad king's guards after only poisoning one bottle. 

Unfortunately, the guards don't know which bottle contains the poison, but they do know that it's potent enough to kill the king even if it's diluted 100,000 times.

Furthermore, it takes a month for the effects to manifest. The evil king decides to have some of his vast dungeons' prisoners drink the wine. As a cunning bad king, he understands that he needs to murder as few prisoners as possible, believing that he can get away with such a low death rate and still drink the rest of the wine (999 bottles) at his anniversary party in 5 weeks.

In the worst-case scenario, how many prisoners would he have to kill in order to discover the poisoned bottle? Keep in mind that the king wants to keep the number of prisoners involved in the experiment as low as possible. He may decide to kill every prisoner involved in the experiment if he believes they will reveal his evil plans to the rest of the world.

Hint: Think of binary representation and combinations.

Get the tech career you deserve, faster!
Connect with our expert counsellors to understand how to hack your way to success
User rating 4.7/5
1:1 doubt support
95% placement record
Akash Pal
Senior Software Engineer
326% Hike After Job Bootcamp
Himanshu Gusain
Programmer Analyst
32 LPA After Job Bootcamp
After Job
Bootcamp

Solution

One can easily say that in the worst-case king will need 1000 prisoners, make every prisoner drink the wine, and whosoever dies will help him find the bottle with poison. So 1000 prisoners and 1 dies, but we have a condition that the king wants to minimize the number of prisoners.

So how to minimize prisoners?

Okay, you must have heard of the binary representation of numbers. So, we will use binary representation here to solve this problem.

First, let's discuss how we represent numbers in binary,

1 in binary 01,

2  in binary  10

3  in binary 11

4  in binary 100

5  in binary 101

6  in binary  110

7  in binary  111

8 in binary  1000

16 in binary 10000

32  in binary  100000

If we closely observe the pattern to represent all numbers that are less than 2we need n bits. To represent numbers less than 4(22), we need 2 bits, to represent numbers less than  8(23) we need 3 bits. And all other numbers less than that power of 2 can be represented with the help of stated bits
 

To represent all numbers less than 512, we will need 9 bits, and for all numbers less than 1024, we will need 10 bits( and with 10, we can represent all numbers less than or equal to 1023). We will make all combinations of 0's and 1's in that 10 places to represent all numbers less than 1024.

Now think of these bits as prisoners' positions. If we make 10 prisoners stand in a row and we have all combinations of binary for each number less than equal to 1000, then it's easy to solve the problem.

Serve the very little amount of wine from each bottle, and make the prisoner drink the wine standing at a particular position for which the set bit at that position is 1(for that particular representation of bottle number).

For example, for bottle 1 we have representation 0000000001 so make one prisoner standing in the right position to drink the wine. For bottle 7, 0000000111, prisoners at position 1,2,3 will have the wine. In this way, all combinations can be made to 1000( since we have 1000 bottles only).

Wine will take 1 month to have an effect, and after that, some prisoners will die, and we can check from our combinations which combination has come into effect. Again the corresponding bottle number can be calculated, which will be the bottle with poisoned wine.

So we will need 10 prisoners, but it has been asked that maximum how many will die. 

Let us now consider the number of prisoners who will perish in the worst-case scenario. That's the maximum number of 1 bits in a number ranging from 0 to 999. The number 511 is made up of 9 1 bits. 2^10 - 1 = 1023 is the first number with ten set bits. Because that is out of our range, a maximum of 9 prisoners, the king will sacrifice or kill for the experiment.

Check out this problem - 8 Queens Problem

Frequently Asked Questions

Can we solve the puzzle for 1022 bottles? Will the answer change?

No, the answer will not change since all numbers less than 1023 will require the same number of bits for their representation.

What will be the best-case scenario( how many minimum prisoners will die)?

The minimum number is 1 prisoner. Only one prisoner drinks the poisoned wine out of 10. It can be any binary permutation in which we have only one set bit.

Why should I practice puzzles?

Puzzles help you to improve your logical and problem-solving skills. Moreover, they are also asked in company interviews.

Do MNCs ask puzzles in the interview of IT companies?

Many tech giants like Google, Microsoft, etc., ask the puzzles in the interview process as they want to check your logical thinking.

From where can I practice more such puzzles?

You can refer to the conclusion section for links to puzzle sections.

Conclusion

In this article, we discussed a famous puzzle, 'prisoners and poison.' We hope that you enjoyed the puzzle, and this blog helped you to understand the puzzle well. If you liked it and want to solve some more, you can check out Top 150 Interview Puzzles

Logical Puzzles:


Pattern Based Puzzles:


Recommended Readings:


Do check out The Interview guide for Product Based Companies as well as some of the Popular Interview Problems from Top companies like Amazon, Adobe, Google, etc. on Coding Ninjas Studio.

Also check out some of the Guided Paths on topics such as Interview Puzzles, Data Structure and Algorithms, Competitive Programming, Operating Systems, Computer Networks, etc. as well as some Contests, Test Series, Interview Bundles, and some Interview Experiences curated by top Industry Experts only on Coding Ninjas Studio.

Happy Learning!

Previous article
Bee Travel
Next article
World Trips
Live masterclass