# Egg Drop Problem Given : n number of eggs. An egg could be dropped from any floor of a building having k floors.

Objective : Find the minimum number of attempts to find out the lowest floor in the building from which if the egg is dropped, would break.

• An attempt consist of dropping an egg from any floor of the building.
• If the egg does not break after dropping it from floor f, it would not break when dropped from the floors below f.
• If the egg breaks after dropping from floor f, it would obviously break when dropped from the floors above f.
• A broken egg cannot be used again.

Note: If all the eggs are broken while attempting to find out the threshold (bottom-most egg-breaking floor), we lose the information from previous attempts.

Example :
1 egg and 3 floors
If the building has 3 floors and we have just 1 egg, then in the worst-case we would need to drop the egg from each of the 3 floors to find out the bottom-most floor that would cause the egg to break.
[ 3 Attempts needed ]

2 eggs and 1 floor
If there is only 1 floor then it would take only 1 attempt for any ( N > 0 ) number of eggs.
Similarly, if there are no floors ( 0 floors ) then there would be 0 attempts.
[ 1 Attempt needed ]

2 eggs and 3 floors
Attempt 1 : We could be smarter by trying the middle floor i.e floor number 2.
If the egg doesn’t break we would go to floor 3.
Attempt 2 : Drop the egg from floor 3 if it breaks, we know the threshold i.e floor 3.
Else If the egg breaks we would go to floor 1.
Attempt 2 : Drop the egg from floor 1, if it breaks, we know the threshold i.e floor 1 if it doesn’t the threshold is floor 2.
[ 2 Attempts needed ]

The egg drop problem could be solved recursively as well as using dynamic programming. Recursion
int Egg_Drops ( eggs, floors )

If ( eggs == 1 )
return floors
If ( floors == 0 or floors == 1 ) then
return floors
Initialize attempt = max number
For the current_floor beginning with 1 upto floors
There are 2 possibilities : Egg breaks or Egg doesn’t break
attempt = min ( attempt, 1 + max [ EggDrops ( eggs - 1, current_floor - 1 ),
EggDrops ( eggs, floors - current_floor ) ] )
return attempt

Time Complexity : The time complexity of the recursive algorithm is O ( 2 floors )

Dynamic Programming
int Egg_Drops ( eggs, floors )

Create cache [ eggs + 1 ] [ floors + 1 ]

Irrespective of the number of eggs, if there is only 1 floor, then it would take just 1 attempt.
Similary if there are no floors ( 0 floors ), then it would take 0 attempts.
For the egg e from 0 upto eggs
cache [ e ] [ 0 ] = 0
cache [ e ] [ 1 ] = 1

If there is only 1 egg, then the attempts would same as the number of floors.
Also if there are no eggs ( 0 eggs ) then there would be 0 attempts.
For the floor f from 0 upto floors
cache [ 1 ] [ f ] = f
cache [ 0 ] [ f ] = 0

For egg e from 2 upto eggs
For floor f from 2 upto floors
cache [ e ] [ f ] = max number
For current_floor from 2 upto f
Attempts = 1 + max ( cache [ e - 1 ] [ current_floor - 1 ], cache [ e ] [ f - current_floor ] )
cache [ e ] [ f ] = min ( cache [ e ] [ f ], Attempts )
return cache [ eggs ] [ floors ]

Time Complexity : The time complexity of the dynamic programming algorithm is O ( eggs . floors 2 )

C++ Finding the minimum egg drop attempts to find the threshold floor.

``````#include<algorithm>
#include<iostream>
#include<climits>
#include<map>

using namespace std;

int EggDrops (int eggs, int floors) {

int cache[eggs+1][floors+1];

// If there are no floors (i.e 0 floors) we would have zero attempts.
// If there is only 1 floor, there would only be 1 attempt.
for (int e=0; e<=eggs; e++) {
cache[e] = 0;
cache[e] = 1;
}

// If there is only 1 egg then we could need attempts
// same as the number of floors in worst case.
// If there are 0 eggs, there would be 0 attempts.
for (int f=0; f<=floors; f++) {
cache[f] = f;
cache[f] = 0;
}

/*
floors  k   |
.   |
.   |
f   | <- If an egg breaks at floor f, then we would need to check the floors below 'f'
f-1  |    to find the bottom-most floor from which an egg if dropped would break.
.   |    i.e (f-1) floors with one less egg from available eggs.
2   |    If the egg doesn't break, then we would need to check the floors above f
1   |    i.e from floor f + 1 till n i.e (k-f) floors with the same number of eggs.

Note : If an egg breaks or it doesn't break, every drop is considered an attempt.
*/

for (int e=2; e<=eggs; e++) {
for (int f=2; f<=floors; f++) {
cache[e][f] = INT_MAX;
for (int current_floor = 2; current_floor <= f; current_floor++) {
// On the current floor there are two possible scenarios (Egg breaks, Egg doesn't break).
int attempts = 1 + max(cache[e-1][current_floor-1], cache[e][f-current_floor]);
cache[e][f] = min(cache[e][f], attempts);
}
}
}

return cache[eggs][floors];
}

map<pair<int, int>, int> cache_map;
int EggDropsRec (int eggs, int floors) {

if (eggs == 1)
return floors;

if (floors == 0 || floors == 1)
return floors;

if (cache_map.find(make_pair(eggs, floors)) != cache_map.end()) {
return cache_map.find(make_pair(eggs, floors))->second;
}

int attempt = INT_MAX;
for (int current_floor=1; current_floor<=floors; current_floor++) {
// Two possibilities
// 1.Egg breaks
// 2.Egg doesn't break
attempt = min(attempt, 1 + max(EggDropsRec(eggs-1, current_floor-1), EggDropsRec(eggs, floors-current_floor)));
}
cache_map.insert(make_pair(make_pair(eggs, floors), attempt));
return attempt;
}

int main() {

int eggs = 2, floors = 300;
cout << "Dynamic Programming" << endl;
cout << "Eggs : " << eggs << " Floors : " << floors << " Attempts required : " << EggDrops(eggs, floors) << endl;
cout << "Recursion" << endl;
cout << "Eggs : " << eggs << " Floors : " << floors << " Attempts required : " << EggDropsRec(eggs, floors) << endl;

eggs = 5, floors = 100;
cout << "\nDynamic Programming" << endl;
cout << "Eggs : " << eggs << " Floors : " << floors << " Attempts required : " << EggDrops(eggs, floors) << endl;
cout << "Recursion" << endl;
cout << "Eggs : " << eggs << " Floors : " << floors << " Attempts required : " << EggDropsRec(eggs, floors) << endl;

return 0;
}
``````

Output

``````Dynamic Programming
Eggs : 2 Floors : 300 Attempts required : 24
Recursion
Eggs : 2 Floors : 300 Attempts required : 24

Dynamic Programming
Eggs : 5 Floors : 100 Attempts required : 7
Recursion
Eggs : 5 Floors : 100 Attempts required : 7
``````