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.
What is a puzzle?
4.2.
How to solve a number sequence puzzle?
4.3.
What are the advantages of solving puzzles?
4.4.
What are some tips for preparing for a puzzle interview?
4.5.
Which are the commonly asked pattern-solving problems in interviews?
5.
Conclusion
Last Updated: Mar 27, 2024

100 Prisoners with Red and Black Hats

Master Python: Predicting weather forecasts
Speaker
Ashwin Goyal
Product Manager @
Interview Puzzles

Introduction

Puzzles are good exercise for the brain. They help in enhancing the cognitive abilities of the brain helping with Problem Solving and related skills. There are numerous types of puzzles; each one having a logic inherent to itself which helps in cracking it. A good puzzle well is actually like a good mystery that we may have read about or watched on TV. It has the finest of hints which help in reaching its solution.

The following article discusses one such puzzle so let's get right to it.

Problem Statement

The 100 prisoners with red and black hats problem is as described below:

One hundred prisoners are lined up single file. A blue or red hat is placed on each of their heads randomly. The prisoners cannot see the color of the hat on their own heads, but they can see the colors of all the hats in front of them. The prisoner in the back can clearly see all 99 hats in front of him. The 50th prisoner in line can see the 49 hats in front of him, and the prisoner in the front of the line cannot see anything but the forest before him. Also, the prisoners don't know the proportion of red hats to blue hats in advance—it could be 50/50, but it could also be any combination that adds to 100.

A guard is going to walk down the line, starting in the back, and ask each prisoner what color hat they have on. They can only answer "blue" or "red." If they answer incorrectly or say anything else, they will be shot dead on the spot. If they answer correctly, they will be set free. Each prisoner can hear all of the other prisoners' responses, as well as any gunshots that indicate an incorrect response. They can remember all of this information.

Before the executions begin, the prisoners get to huddle up and make a plan. How can the prisoners ensure that the most people possible survive?

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

With the right plan, you can guarantee that 99 of the prisoners will live, and the remaining prisoner will have a 50% chance. The key is to find a piece of information that the first prisoner can convey using only the words "blue" or "red," a piece of information with only two possibilities.

The prisoners come up with the following plan: If the first prisoner to speak—the one in the back of the line—sees an even number of blue hats, he will yell out "blue." If he sees an odd number of blue hats, he will yell out "red."

Let's assume the first prisoner to speak yells out "blue," indicating that he sees an even number of blue hats. Then the next prisoner to speak can look at the line in front of him, and if he sees an odd number of blue hats, he knows his hat must be blue to make the number even. Similarly, if he sees an even number of blue hats, he knows his hat must be red to keep it that way. The same logic works if the first prisoner yells out "red," indicating that there are an odd number of blue hats.

The next prisoner in line listens to the prisoner behind him, and takes that information into consideration. If he sees an even number of blue hats and the prisoner behind him yells "blue," making the total number of blue hats odd, then he knows his hat must be blue to make the total number even again (of the 99 seen by the first prisoner). In the same situation, if his hat were red, the total number of blue hats would be odd (of the 99 seen by the first prisoner).

As you go down the line, each prisoner must count how many blue hats are behind them. Then he must consider the blue hats in front of him. If the number of blue hats behind a prisoner plus the blue hats he can see in front of him equals an odd number, then he knows his hat must be blue to make the total number even, or red to make the total number odd (not counting the very first prisoner).

The very first prisoner is the maybe-martyr of the group. He is imparting information to the rest of the group that has nothing to do with the hat on his own head, which he cannot know, and so his chances of living are only 50%.

Editor's Note: If the number of blue hats the first prisoner sees is odd, that means the number of red hats is even. So it is also accurate to say the first prisoner yells out "blue" if he sees an even number of blue hats and "red" if he sees an even number of red hats.

Frequently Asked Questions

What is a puzzle?

A puzzle is a game of words, toys, questions, etc. that helps in increasing our problem-solving ability.

How to solve a number sequence puzzle?

To solve a number sequence puzzle, first, find the pattern between numbers of the sequence. Once you know the pattern then you can find the next number of the sequence by following the same pattern.

What are the advantages of solving puzzles?

Solving puzzles enhance the problem-solving skills of a person. It also improves the logic building of a person.

What are some tips for preparing for a puzzle interview?

Practice, always keep a pen and paper with you and elaborate your approach.

Which are the commonly asked pattern-solving problems in interviews?

In interviews, the commonly asked pattern-solving problems are Hollow Diamond Star Pattern, Inverted V-shape Number Pattern, Matrix in Reverse Spiral Form, etc.

Conclusion

In this article, we discussed the interview-based puzzle. The puzzle is based on 100 prisoners with red and black hats. We also discussed the solution to the given puzzle in the article above in various languages.

Recommended Readings:


For more information, refer to Free Interview Preparation resources.

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 Data Structure and Algorithms, Competitive Programming, Operating Systems, Computer Networks, DBMS, System Design, etc. as well as some Contests, Test Series, Interview Bundles, and some Interview Experiences curated by top Industry Experts only on Coding Ninjas Studio.

Do upvote our blog to help other ninjas grow.

Happy Learning!
 

Previous article
The Knight and the Shortest Path
Next article
100 People in a Circle with a Gun
Live masterclass