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: Egg Dropping Puzzle Using 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

C

C++

Python

Java

Javascript

C

#include <stdio.h> #include <limits.h>

int eggDrop(int eggs, int floors) { if (floors <= 1) return floors; if (eggs == 1) return floors;

int result = INT_MAX; for (int currentFloor = 1; currentFloor <= floors; currentFloor++) { int movesForUnbrokenEggs = eggDrop(eggs, floors - currentFloor); int movesForBrokenEggs = eggDrop(eggs - 1, currentFloor - 1); int worstCase = 1 + ((movesForUnbrokenEggs > movesForBrokenEggs) ? movesForUnbrokenEggs : movesForBrokenEggs); result = (result < worstCase) ? result : worstCase; } return result; }

int main() { int eggs, floors; printf("Enter Eggs: "); scanf("%d", &eggs); printf("Enter Floors: "); scanf("%d", &floors); printf("Minimum number of moves required: %d", eggDrop(eggs, floors)); return 0; }

C++

#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); }

Python

def eggDrop(eggs, floors): if floors <= 1: return floors if eggs == 1: return floors

result = float('inf') for currentFloor in range(1, floors + 1): movesForUnbrokenEggs = eggDrop(eggs, floors - currentFloor) movesForBrokenEggs = eggDrop(eggs - 1, currentFloor - 1) worstCase = 1 + max(movesForUnbrokenEggs, movesForBrokenEggs) result = min(result, worstCase) return result

eggs = int(input("Enter Eggs: ")) floors = int(input("Enter Floors: ")) print("Minimum number of moves required:", eggDrop(eggs, floors))

Java

import java.util.Scanner;

public class EggDrop { public static int eggDrop(int eggs, int floors) { if (floors <= 1) return floors; if (eggs == 1) return floors;

int result = Integer.MAX_VALUE; for (int currentFloor = 1; currentFloor <= floors; currentFloor++) { int movesForUnbrokenEggs = eggDrop(eggs, floors - currentFloor); int movesForBrokenEggs = eggDrop(eggs - 1, currentFloor - 1); int worstCase = 1 + Math.max(movesForUnbrokenEggs, movesForBrokenEggs); result = Math.min(result, worstCase); } return result; }

public static void main(String[] args) { Scanner scanner = new Scanner(System.in); System.out.print("Enter Eggs: "); int eggs = scanner.nextInt(); System.out.print("Enter Floors: "); int floors = scanner.nextInt(); System.out.println("Minimum number of moves required: " + eggDrop(eggs, floors)); } }

Javascript

function eggDrop(eggs, floors) { if (floors <= 1) return floors; if (eggs == 1) return floors;

let result = Infinity; for (let currentFloor = 1; currentFloor <= floors; currentFloor++) { let movesForUnbrokenEggs = eggDrop(eggs, floors - currentFloor); let movesForBrokenEggs = eggDrop(eggs - 1, currentFloor - 1); let worstCase = 1 + Math.max(movesForUnbrokenEggs, movesForBrokenEggs); result = Math.min(result, worstCase); } return result; }

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.

int eggDrop(int eggs, int floors) { if (floors <= 1) return floors; if (eggs == 1) return floors; if (memo[eggs][floors] != -1) return memo[eggs][floors];

int ans = INT_MAX, movesForUnbrokenEggs = 0, movesForBrokenEggs = 0; int low = 1, high = floors;

if (movesForBrokenEggs > movesForUnbrokenEggs) high = mid; else low = mid + 1;

int temp = 1 + ((movesForBrokenEggs > movesForUnbrokenEggs) ? movesForBrokenEggs : movesForUnbrokenEggs); ans = (ans < temp) ? ans : temp; }

return memo[eggs][floors] = ans; }

int main() { int eggs, floors; printf("Enter Eggs: "); scanf("%d", &eggs); printf("Enter Floors: "); scanf("%d", &floors);

memset(memo, -1, sizeof(memo));

printf("Minimum number of moves required: %d", eggDrop(eggs, floors)); return 0; }

C++

#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; }

if movesForBrokenEggs > movesForUnbrokenEggs: high = mid else: low = mid + 1

temp = 1 + max(movesForBrokenEggs, movesForUnbrokenEggs) ans = min(ans, temp)

memo[eggs][floors] = ans return ans

eggs = int(input("Enter Eggs: ")) floors = int(input("Enter Floors: ")) print("Minimum number of moves required:", eggDrop(eggs, floors))

Java

import java.util.Scanner;

public class EggDrop { static int[][] memo = new int[101][10001];

public static int eggDrop(int eggs, int floors) { if (floors <= 1) return floors; if (eggs == 1) return floors; if (memo[eggs][floors] != -1) return memo[eggs][floors];

int ans = Integer.MAX_VALUE, movesForUnbrokenEggs = 0, movesForBrokenEggs = 0; int low = 1, high = floors;

rl.question("Enter Eggs: ", (eggs) => { rl.question("Enter Floors: ", (floors) => { for (let m of memo) { m.fill(-1); } console.log("Minimum number of moves required: " + eggDrop(parseInt(eggs), parseInt(floors))); rl.close(); }); });

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?

The egg dropping problem is solved using dynamic programming. Recursively explore scenarios of dropping eggs from different floors, memoize results, and return the minimum attempts needed to solve.

What are the different methods of egg drop problem?

Different methods for solving the egg drop problem include dynamic programming, binary search, and mathematical optimization. Each method offers unique trade-offs in terms of complexity and efficiency.

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.