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] = 0;
cache[e][1] = 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[1][f] = f;
cache[0][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