Data structures & algorithms (Beginner to Intermediate)

Free guided path13 chapters99+ problems

Earn badges and level up

Introduction

Egg dropping problem is a very famous coding problem that requires a bit thinking. The problem statement is as follows. We are given a multi story building, and some number of eggs. We want to know from which floors, if we drop a egg, it will break.

It’s a Monday in Coders’ world. You are about to get a new problem. There is a building with floors 1 to ‘FLOORS’. You are given a basket full of identical eggs. ‘EGGS’ identical eggs. For a better understanding, refer to the figure given below.

As the eggs are identical, they follow the same properties. These properties are given below:

Each egg breaks only if it is dropped from a certain floor ‘EGGBREAKER’ or above.

An egg that is not broken after being dropped from a floor can be used to drop again.

As discussed in the introduction section, you are given the following details:

‘FLOORS’: Total number of floors in the building.

‘EGGS’ : Total number of eggs in the basket.

Your task is to find the minimum number of egg drops required in the worst case to find out the ‘EGGBREAKER’ floor.

Dropping from different floors leads to a different number of moves required to find the ‘EGGBREAKER’ floor.

Input

Enter Eggs: 2
Enter Floors: 6

Output

Minimum number of moves required: 3

Get the tech career you deserve, faster!

Connect with our expert counsellors to understand how to hack your way to success

User rating 4.7/5

1:1 doubt support

95% placement record

Akash Pal

Senior Software Engineer

326% Hike After Job Bootcamp

Himanshu Gusain

Programmer Analyst

32 LPA After Job Bootcamp

After Job Bootcamp

Method 1: Recursion

Recursion is all about using a top-down approach. Every recursion solution recipe has the following ingredients:

Step 1: A problem with bigger input is broken down into the same problem with smaller inputs.

Step 2: The process keeps repeating until the breakdown is not possible anymore. In other words, recursion stops when we hit the base case.

Step 3: The outputs of smaller problems are combined to compute problems with bigger inputs.

Can we use recursion for the given problem? Let’s see if our unique Egg dropping problem contains all the ingredients for our recursion recipe.

A part of the building is also a type of smaller building. Similarly, a subset of eggs from the basket can also be considered as a smaller input. Thus, a problem with a larger input can be divided into subproblems with smaller inputs. Recursive calls create subproblems. Consider an egg dropped from a certain floor (say ‘CURRENT_FLOOR’). Whatever the outcome be, possible next moves are as follows: a. The egg broke after falling from the ‘CURRENT_FLOOR’. We can drop the next egg from a floor smaller than ‘CURRENT_FLOOR’. The ‘EGGS’ is decreased by 1. For this, the recursive call is FUNCTION(‘CURRENT_FLOOR’ - 1, ‘EGGS’ - 1) b.The egg did not break after falling from the ‘CURRENT_FLOOR’. ‘EGGS’ is still the same. Drop the egg from the floor above the ‘CURRENT_FLOOR’. For this, the recursive call is 2. FUNCTION(‘FLOORS’ - ‘CURRENT_FLOOR’, ‘EGGS’ )

Can you guess the base case? This problem has two following base cases: a. If ‘EGGS’ is equal to 1, then the only way to find out the ‘EGG_BREAKER’ floor is by starting to drop the egg from the 1st floor to all the way up. b. If ‘TOTAL_FLOOR’ is equal to 1, then only one egg drop is required to find if it is an ‘EGG_BREAKER’ floor. Also, if the ‘TOTAL_FLOOR’ is equal to 0, then no egg drop is required as no ‘EGG_BREAKER’ floor is possible.

How to combine outputs of all the subproblems? As discussed in the Understanding the Problem section, we need to find the minimum number of egg drops in the worst case. For the worst case, find the maximum of all the outputs of the recursive calls for ‘CURRENT_FLOOR’. To find the minimum number of egg drops for the given ‘FLOORS’ and ‘EGGS’, return the minimum of the result of egg drops from all the floors.

The problem has all the ingredients for our recursion recipe. Refer to the algorithm given below for a better understanding.

Algorithm

If ‘FLOORS’ is less than or equal to 1, then:

Return ‘FLOORS’.

If ‘EGGS’ is equal to 1, then:

Return ‘EGGS’ .

Set ‘RESULT’ equal to the maximum value possible (INT_MAX).

Loop ‘CURRENT_FLOOR’ from 1 to ‘FLOORS’.

Set ‘MOVES_FOR_UNBROKEN_EGGS’ = recursive call with arguments (‘FLOORS’ - ‘CURRENT_FLOOR’ , ‘EGGS’ ).

Set ‘MOVES_FOR_BROKEN_EGGS’ = recursive call with arguments (‘CURRENT_FLOOR’ - 1, ‘EGGS’ - 1).

Set ‘WORST_CASE’ = 1 + max(‘MOVES_FOR_UNBROKEN_EGGS’ , ‘MOVES_FOR_BROKEN_EGGS’ ). (1 is added to count the current move).

Set ‘RESULT’ = min(‘RESULT’ , ‘WORST_CASE’ ).

Return ‘RESULT’

Program

#include <iostream>
#include <limits.h>
using namespace std;
int eggDrop(int eggs, int floors)
{
// Base Case.
if (floors <= 1)
return floors;
if (eggs == 1)
return floors;
int result = INT_MAX;
for (int currentFloor = 1; currentFloor <= floors; currentFloor++)
{
// Recursive Calls.
int movesForUnbrokenEggs = eggDrop(eggs, floors - currentFloor);
int movesForBrokenEggs = eggDrop(eggs - 1, currentFloor - 1);
// Choosing the worst case from the recursive calls.
// Adding 1 for the move to make a recursive call.
int worstCase = 1 + max(movesForUnbrokenEggs, movesForBrokenEggs);
// Comparing moves required in the worst case to the minimum number of moves required in all the cases.
result = min(result, worstCase);
}
return result ;
}
int main()
{
int eggs, floors;
cout << "Enter Eggs: ";
cin >> eggs;
cout << "Enter Floors: ";
cin >> floors;
cout << "Minimum number of moves required: " << eggDrop(eggs, floors);
}

Input

Enter Eggs: 2
Enter Floors: 6

Output

Minimum number of moves required: 3

Complexity Analysis:

Time complexity: Two recursive calls are made for every combination of eggs and floors. So, the total number of recursive calls is 2^{min(EGGS, FLOORS)}. A loop runs in the code in linear time from 1 to ‘FLOORS’ for each recursive call. So, the time complexity of code is O(FLOORS * 2^{min(EGGS, FLOORS) }).

Space complexity: Since the total number of recursive calls is 2^{min(EGGS, FLOORS)}. The depth of the recursion tree would be min(EGGS, FLOORS). Therefore, the total space complexity required due to recursive call stack is O(min(EGGS, FLOORS)).

A recursion is a straightforward approach, but it gives a TLE when brought to use. Take a look at the recursion tree shown in the figure below. For simplicity, we are considering only one floor as the current floor.

With the increase in the size of the recursive tree, the recursive function is called multiple times with the same input argument. Memoization can prune the recursive tree by storing the results of recursive calls. All you need to do is to make some tiny changes in our recursion recipe.

What should we memoize? You might have noticed that the output depends on ‘FLOORS’ and ‘EGGS’ for every function call. The maximum number of ‘FLOORS’ - ‘EGGS’ pairs is possible as the function arguments are (‘FLOORS’ + 1) x (‘EGGS’ + 1). We can use a 2-D (say ‘MEMO’’) array to store the output of these possible pairs. Extra row and column is added because the array is 0-indexed and arguments are 1-indexed.

Can we optimize it more? Yes, we can. In the Method 1:Recursion section, we used a linear search to check if the ‘CURRENT_FLOOR’ is an ‘EGG_BREAKER’ floor. This linear search runs in O(‘FLOOR’) time. The linear search can be replaced as binary search for further optimization. These minor modifications in our recursion algorithm can help us avoid the exponential time complexity. Refer to the algorithm given below for a better understanding.

Algorithm

Initialize a ‘MEMO’ vector of size (‘FLOORS’ + 1) x (‘EGGS’ + 1) with value -1.

If ‘FLOORS’ is less than or equal to 1, then:

Return ‘FLOORS’.

If ‘EGGS’ is equal to 1, then:

Return ‘EGGS’ .

If MEMO[‘FLOORS’ ][‘EGGS’ ] is not equal to -1, then:

Return MEMO[‘FLOORS’ ][‘EGGS’ ]

Set ‘RESULT’ equal to the maximum value possible (INT_MAX).

Set ‘LOW’ = 1 and ‘HIGH’ = ‘FLOORS’ for binary search.

While ‘LOW’ < ‘HIGH’, do:

Set ‘MID_FLOOR’ = ‘LOW’ + (‘HIGH’ - ‘LOW’ ) / 2

Declare ‘MOVES_FOR_UNBROKEN_EGGS’.

If MEMO[‘FLOORS’ - ‘MID_FLOOR’ ][‘EGGS’] is equal to -1, then:

Set ‘MOVES_FOR_UNBROKEN_EGGS’ = recursive call with arguments (‘FLOORS’ - ‘MID_FLOOR’, ‘EGGS’ ).

Else:

Set ‘MOVES_FOR_UNBROKEN_EGGS’ = MEMO[‘FLOORS’ - ‘MID_FLOOR’ ][‘EGGS’].

Declare ‘MOVES_FOR_BROKEN_EGGS’.

If MEMO[‘MID_FLOOR’ - 1][‘EGGS’ - 1] is equal to -1, then:

Set ‘MOVES_FOR_BROKEN_EGGS’ = recursive call with arguments (‘MID_FLOOR’ - 1, ‘EGGS’ - 1).

Else:

Set ‘MOVES_FOR_BROKEN_EGGS’ = MEMO[‘MID_FLOOR’ - 1][‘EGGS’ - 1]

If ‘MOVES_FOR_BROKEN_EGGS’ < ‘MOVES_FOR_UNBROKEN_EGGS’, then:

Set ‘LOW’ = ‘MOVES_FOR_BROKEN_EGGS’ + 1.

Else:

Set ‘HIGH’ = ‘MOVES_FOR_UNBROKEN_EGGS’.

Set ‘WORST_CASE’ = 1 + max(‘MOVES_FOR_BROKEN_EGGS’, ‘MOVES_FOR_UNBROKEN_EGGS’).

Set ‘RESULT’ = min(‘RESULT’, ‘WORST_CASE’ ).

Before Return, Set MEMO[‘FLOORS’ ][‘EGGS’ ] = ‘RESULT’.

Return ‘RESULT’

Program

#include <iostream>
#include <climits>
#include <vector>
#include <cstring>
using namespace std;
int memo[101][10001];
int eggDrop(int eggs, int floors)
{
// If 'FLOORS' = 0 no drop needed.
// If FL'OORS = 1 only 1 drop needed.
if (floors <= 1)
return floors;
// If 'EGGS' = 1, gradually drop the egg from 1st floor to all the way up.
if (eggs == 1)
return floors;
// If answer for given number of eggs and floors, return it.
if (memo[eggs][floors] != -1)
return memo[eggs][floors];
// 'ANS' returns the final answer for current number of eggs and floors.
int ans = INT_MAX, movesForUnbrokenEgss = 0, movesForBrokenEgss = 0;
// 'LOW' and 'HIGH' pointers for binary search.
int low = 1, high = floors;
while (low < high)
{
// Computing mid floor to drop the egg from the mid floor.
int mid = low + (high - low) / 2;
// 'MOVES_FOR_BROKEN_EGGS' to store answer if egg is broken after falling from 'MID' floor.
if (memo[eggs - 1][mid - 1] != -1)
movesForBrokenEgss = memo[eggs - 1][mid - 1];
else
movesForBrokenEgss = eggDrop(eggs - 1, mid - 1);
// 'MOVES_FOR_UNBROKEN_EGGS' to store answer if egg is not broken after falling from 'MID' floor.
if (memo[eggs][floors - mid] != -1)
movesForUnbrokenEgss = memo[eggs][floors - mid];
else
movesForUnbrokenEgss = eggDrop(eggs, floors - mid);
// Move the binary search towards the case where number of egg drops are more.
if (movesForBrokenEgss > movesForUnbrokenEgss)
high = mid;
else
low = mid + 1;
// Maximum number of egg drops for both the case.
// Add 1 to represent the current egg drop.
int temp = 1 + max(movesForBrokenEgss, movesForUnbrokenEgss);
// Choose minimum of all the worst cases.
ans = min(ans, temp);
}
// Storing the output for current numbers of eggs and floors.
return memo[eggs][floors] = ans;
}
int main()
{
int eggs, floors;
cout << "Enter Eggs: ";
cin >> eggs;
cout << "Enter Floors: ";
cin >> floors;
// Initialize memo array with value -1.
memset(memo, -1, sizeof(memo));
cout << "Minimum number of moves required: " << eggDrop(eggs, floors);
}

Complexity Analysis

Time Complexity: A binary search is done for every combination of the number of eggs and floors. The maximum number of combinations possible is K x N, where ‘K’ and ‘N’ represent the number of eggs and floors. The time complexity of a binary search operation is log(N), where ‘N’ represents the number of floors given. O(K x NlogN), where ‘K’ and ‘N’ represent the number of eggs and floors respectively.

Space Complexity: Additional space is required to store the results of the recursive function in the memo. The size of the memo depends on the number of eggs and floors given in the input. So, the space complexity is O(K x N), where ‘K’ and ‘N’ represent the number of eggs and floors, respectively.

Egg dropping problem is a very famous coding problem that requires a bit thinking. The problem statement is as follows. We are given a multi story building, and some number of eggs. We want to know from which floors, if we drop a egg, it will break.

How do you solve an egg dropping problem?

There are many different methods to solve an egg dropping problem. In order to find the least number of droppings required in the worst case, try dropping an egg from each floor. A component of the solution will be the floor that provides the least value under the worst-case scenario.

What are the different methods of egg drop problem?

To solve egg dropping problem, there are many methods. One of the method is to solve using recursion. We can see that an optimal substructure property to solve the problem. We can also use the dynamic programming approach to solve the problem. It will reduce the time complexity by a lot.

Conclusion

There’s usually more than one approach to a solution. Yes, it feels sluggish to solve the same problem again and again. But, we should always try to look for more ways to solve a problem. After all, it’s an excellent way to practice more than one algorithm or technique from a single problem.

Try to memoize the code if some value is computed again and again. To become a good coder, you need other ingredients too. You need to have a common sense with a bit of mind that’s ready to make adjustments to a solution. Adjustments that can make it more efficient. You can practice memoization and many more cool techniques using our free practice platform Coding Ninjas Studio. So, keep practicing. That’s what good coders do.