Egg Dropping Problem
You are given N eggs, and building with K floors from 1 to K. Each egg is identical, you drop an egg and if an egg breaks, you cannot drop it again. You know that there exists a floor F with 0 <= F <= K such that any egg dropped at a floor higher than F will break, and any egg dropped at or below floor F will not break. Each move, you may take an egg (if you have an unbroken one) and drop it from any floor X (with 1 <= X <= K). Your goal is to know with certainty what the value of F is.
What is the minimum number of moves that you need to know with certainty what F is, regardless of the initial value of F?
The first line of the input is T denoting the number of test cases. Then T test cases follow. Each test case contains one line denoting N number of eggs and K denoting K number of floors.
For each test case output in a new line the minimum number of attempts that you would take. F(F>=1 and F<=k).
Example with explanation:
Input: T=1 N=1 K=2 Output: 2 Drop the egg from floor 1. If it breaks, we know with certainty that F = 0. Otherwise, drop the egg from floor 2. If it breaks, we know with certainty that F = 1. If it didn't break, then we know with certainty F = 2. Hence, we needed 2 moves in the worst case to know what F is with certainty. Input: T=1 N=2,K=100 Output: 14 Minimum number of trials that we would need is 14 to find the threshold floor F.
1) Recursive Approach:
We have n eggs and k floors. The following are the possibilities,
When we drop an egg from a floor x, there can be two cases (1) The egg breaks (2) The egg doesn't break.
Since we need to minimize the number of trials in the worst case, we take the maximum of two cases. We consider the max of the above two cases for every floor and choose the floor which yields the minimum number of trials.
The time complexity for the above approach is exponential hence it is valid only for a smaller number of inputs.
2) Dynamic Programming Approach
Here will declare the state of our dynamic programming as dp[n][k] where n is the number of eggs we have and k is the floor we have at any instant of the moment.
There are base cases,
dp[i]=0 if there is no egg then simply the answer is 0.
dp[i]=i if we have 1 egg then in the worst case we have to attempt all the floor to get the min number of attempts in the worst case.
We will see both of the approach top-down and bottom-up approach.
Initially, we will fill all dp[n][k] with -1 for memorization approach.
So, that if it is calculated then return it immediately without calculating it again.
2.1) Top Down Approach
Time Complexity for the above approach in the worst case is O(nk^2).
Space Complexity for the above approach in the worst case is O(nk).
2.2) Bottom Up Approach
Time Complexity for the above approach is O(n*k^2).
Space Complexity for the above approach is O(nk).need an explanation for this answer? contact us directly to get an explanation for this answer