Egg Dropping Puzzle
Egg Dropping Puzzle
The egg dropping puzzle problem is a famous problem that requires dynamic programming to solve optimally. It is asked in various coding interview and coding rounds. In this article, we provide a C++ solution with an explanation.
Egg Dropping Puzzle Problem Description
Given n numbers of eggs and a building with k number of floors. The building has a limit up to which if we drop, the egg does not break. We have to determine the minimum number of egg drops required to find the limit in the worst case.
- Single line input containing two integers n & k.
- Single integer the required number of egg drops.
Egg Dropping Puzzle Problem Solution Explanation
Solution (Top Down):
To build a top-down solution we must follow the following steps –
Break Down the Problem – Consider we have a function F(e,f) which outputs the minimum number of egg drops/attempts with e eggs required to find the limiting floor of a building with f floors. How to breakdown the problem? For every floor k in the building, we have two choices –
- If the eggs break, then we recursively call for f(e-1,k-1) because we have 1 less egg and since the breaks, we know the required floor must be below it.
- If the egg doesn’t break, then we recursively call for f(e,f – k) because we have the same number of eggs, and since the egg didn’t break we know our answer must lie above this floor. So, the number of floors above kth floor are f – k.
We will repeat this for k belonging to [ 1 , f ] .(Remember that we have to minimize the number of attempts in the worst case!) Answer for every k is the maximum of the above two options. since we have to minimize our overall answer, we will take the minimum out of every possible answer of every kth floor.
Find the base case – The base case is the solution to the smallest known problem. The base cases are –
- If we have 0 number of floors, then we require 0 egg drop to know whether the egg breaks or not.
- If we have 1 number of floors, then we require 1 egg drop to know whether the egg breaks or not.
- If we have 1 egg left, then in the worst case the limiting floor should be at the top and to determine it we will keep on throwing the egg from the bottom to top.
Check for optimal substructure and overlapping subproblems – It is easy to see that the problem can be broken down into smaller problems.
Solution (Bottom Up):
The bottom-up solution is similar to the above. We create a dp table of size (n+1,k+1) and fill the base cases. After filling base cases we fill the table iteratively.