Find out the strength of the eggs

♠ Posted by GeekyFry in , at 10:04 AM

You have two identical eggs. Standing in front of a 100 floor building, you have to find out what is the maximum number of floors from which the egg can be dropped without breaking it. What is the minimum number of tries needed to find out the solution?



Solution:
Most simplistic and idiotic solution
Start at 1st Floor and drop the egg from there. If it breaks, you got the answer. If not, go to the next floor and repeat the process.
If this were to be the soltution, we didn’t need brains in our head. Isn’t it ?  :D
Still for the sake of building better answer, let’s find out the worst case scenario. In this case if the egg was to break from 100th floor, it would take 100 trials.
Let us build on it, we can go in steps of 2, that way the worst case scenario would be 50
Now let us take the steps of 3, So suppose in this case if the egg breaks on floor #9, then already we have taken 3 trials (3rd, 6th & 9th Floor) and now another 2 chances are required to find out if it would break from 7th or 8th floor. (we need to go from last trial floor number i.e. 6th till 9th floor one at a time in ascending order). Why? Juggle your head a bit ;)  (We got just one more egg to break to arrive at the right answer, remember?)
A nice solution
Going and learning from the above answers, we can now figure out the relation between step number(interval) and number of trials (worst case). This can be given as below:
Interval – Maximum tries
1 – 100
2 – 51
3 – 35
4 – 29
5 – 25
6 – 21
7 – 20
8 – 19
9 – 19
10 – 19
11 – 19
12 – 19
13 – 19
14 –  20
15 –  20
16 –  21

So with this table in hand, we can say that the best case scenario would be 19 trials. This would be a decent answer.
But can we optimize this more? Read on…
A better solution
Instead of having a fixed interval, we can actually have variable interval. Let us start with 14th floor. If the egg breaks at 14th floor, we need another 13 trials (from 1st till 13th floor) to find out the right floor number from where the egg breaks (worst case scenario of 13 being the answer). So total number of trials will be equal to the interval chosen = 14
Now, if the the egg doesn’t break from the 14th floor, the next interval we should choose is 1 less than the previous interval = 13. That mens we should try from 14 + 13 = 27th floor. If it breaks we need another 12 trials in the worst case to find the exact floor number. This makes the total number of trials in the worst case = 2 + 12 = 14. (1 for trial from 14th floor, 2 for trial from 27 + 12 more trials if the egg broke from 27th floor).
If the egg doesn’t break from27th floor, we can try 39 (27 + 12) and so on. Using 14 as the initial floor, we can reach up to floor 105 (14 + 13 + 12 + … + 1) before we need more than 14 tries. Since we only need to cover 100 floors, 14 trials is sufficient to find the solution.
So answer should be 14 trials

0 comments:

Post a Comment