
Introduction
In this article, we will go through the Wizards and The Dwarfs Puzzle Question.
These types of questions are often asked in Interviews. So, we will be going through the problem statement and then analyzing it to get a better understanding.
Problem Statement
There is a village of wizards and a village of N dwarves.
Once a year, the wizards go over to the village of dwarves and line all the dwarves up in increasing height order, such that each Dwarf can only see the dwarves shorter than himself.
The wizards have an infinite supply of white and black hats. They place either a white or black hat on the head of each Dwarf. Then, starting with the tallest Dwarf (in the back of the line), they ask each what color hat he is wearing. If the dwarf answers incorrectly, the wizards kill him (the other dwarves can hear his response but can't tell if he was killed or not). What is the most number of dwarves killed using this optimal strategy?
Note that the dwarves already know that the wizards will do as stated above. So, they can get together and devise an optimal strategy to minimize the people that get killed.
- Case 1: Answer is a function of N. Output it with N with multipliers or divisor numbers following N. For example, N * 2, N / 2, N * 3 / 4.
- Case 2: The answer is an integer. Just put the number without any decimal places if it's an integer. If the answer is Infinity, output Infinity.
- Case 3: Floating point number. Round it off to 2 decimal places and output it as I. xx, where I is the integer part of the answer, and xx are two decimal digits after rounding off.