## 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!