**Question:** You are given 2 identical eggs such that eggs always break if dropped from floors above a particular floor of a 100-storey building. You need to find that particular floor in minimum number of egg droppings.

**Answer:** What would be the minimum number of drops in worst case if we have only one egg. We have to drop the egg from every floor starting from 1st floor up to 100^{th}. So in worst case scenario, number of droppings will be 100.

And What would be the minimum number of drops in worst case if we have infinite supply of eggs. In that case, we can follow a binary search approach; drop from 50^{th} floor, if broken drop from 25^{th} else from 75^{th} and so on. So in this case, minimum number of drops will be 7 (log_{2}100) in worst case.

^{th}floor; if egg doesn't break then drop from 20

^{th}else start from 1 to 9. Now if the egg breaks from 20

^{th}floor, we need to check only for floors 11

^{th}to 19

^{th}. In worst case, there will be 19 drops for floor number 10, 20, 30, 40, 50, 60, 70, 80, 90, 100, 91, 92, 93, 94, 95, 96, 97, 98, 99.

If we want optimal results, we should divide the building such that for every additional drop, remaining max drop decreases by 1. If our starting floor for first egg is 'k', there are 2 cases:

**The egg breaks:**In this case, total number of drops will be 1 + (k-1) i.e. k as we have to drop from each floor from 1 to (k-1).

**The egg doesn't break:**In this case, we are remaining with (100-k) floors and for optimal performance, max number of drops should be k. Also we verified that the egg doesn't break till k floors, so we need to check floors (k+1) to 100. If we choose i

^{th}floor for 2nd drop of first egg again and egg breaks here, then max droppings needed = 1 + (i-k) (1 for k

^{th}floor in first attempt and (i-k) for (k+1)

^{st}to i

^{th}floor)

As we have discussed it should be equal to k.

k = 1 + (i-k)

i = 2k - 1

This means i

^{th}floor is (k-1) floors above kth. So this tell us that every time, we need to go up by (f-1) floors, where f is floors went up in last drop.

This means that for minimum droppings, egg should be dropped after k floors, then (k-1) floors, then (k-2) floors and so on. The sum of this series should equal 100 and last entry in this series should be 1.

k + (k-1) + (k-2) ... + 1 = 100

k(k+1)/2 = 100

k2 + k - 200 = 0;

k2 + k + (0.5)2 = 200 + (0.5)2

(k + 0.5)2 = 200.25

k = 200.25 1/2 - 0.5

k = 13.65

Since floor can not be in fraction, we need our first drop from 14t

^{th}floor then from (14 + 13 =) 27

^{th}, then (27 + 12 =) 39

^{th}and so on. Also for 2 eggs,

**maximum number of droppings will be 14**.

**How to solve for generalized case?**

We can see that if we drop an egg form k

^{th}floor, there are 2 possibilities:

then we have (k-1) floors and 1 less egg.egg breaks:

then we have (100-k) floors and same number of eggs.egg doesn't break:

We can apply this logic to any number of building and any number of floors.

**Code:**

A recursive solution is quite easy. If maxdrop(f, e) implies maximum drops with 'e' eggs for a 'f' floor building then:

maxdrop(F, E) = for k from 1..F minimum of

1 + MAX(

maxdrop(F-k, E), //if egg doesn't break

maxdrop(k-1, E-1) // if egg breaks

)

but there will be many redundant calls while calculating this. So lets go for a dynamic programing approach and save previously calculated maxdrop(f, e).

#include <iostream> using namespace std; #define max(a,b) (a>b?a:b) int min_num_drops(int num_floors, int num_eggs) { int min_throws[num_floors+1][num_eggs+1]; int f, e, i; if (num_eggs == 1) return num_floors; for(i=0; i<num_floors+1; i++){ min_throws[i][1] = i; min_throws[i][0] = 0; } for(i=0; i<num_eggs+1; i++) { min_throws[0][i] = 0; min_throws[1][i] = 1; } for(e=2; e<=num_eggs; e++) { for(f=2; f<=num_floors; f++) { min_throws[f][e] = INT_MAX; for(i=1; i<=f; i++) { int drops = 1 + max(min_throws[i-1][e-1], min_throws[f-i][e]); if(drops < min_throws[f][e]) min_throws[f][e] = drops; } } } return min_throws[num_floors][num_eggs]; } int main() { int num_floors, num_eggs; cout << "Enter number of floors: "; cin >> num_floors; cout << "Enter number of eggs: "; cin >> num_eggs; cout << "minimum number of drops: " << min_num_drops(num_floors, num_eggs) << endl; }

**Subscribe**- To get an automatic feed of all future posts subscribe here, or to receive them via email go here and enter your email address in the box. You can also like us on facebook and follow me on Twitter @akashag1001.
muraliwhy k should equal to 1+(i-k) please explain it clearly..if possible in another manner..

Akash@murali: As we discussed that we need 1 + (i-k) drops to test floor till ith given first egg is safe till kth floor and breaks from ith floor, where i>k.

Now for optimal drops, at every level, our max number of drops should be equal. We already discovered that for first block of k floor, max number of drops are k. That's the reason, I wrote:

k = 1 + (i-k)

murali@Akash Thanks... now i understood

if u have time please post some articles on unix/linux/os

and design patterns videos r not available...

Thanks

AkashHi Murali,

I will try to add more articles on unix/linux/os as per your request.

Design pattern videos were youtube videos, which are taken down by the author. That's the reason, they are not accessible any more. I will check if I get some other link.

muraliThank You

Ayush"Now for optimal drops, at every level, our max number of drops should be equal."

Can you please share explain this?

AnonymousAt the end, the value of res is 36. But, I dont understand how the value of eggFloor[2][36] is 8.

sidWhat does the following code mean?

res = max(eggDrop(n-1, x-1), eggDrop(n, k-x));

if (res < min)

min = res;

}

Padhma