# 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**?

**Input:**

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.

**Output:**

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

eggs and k floors. The following are the possibilities,nWhen we drop an egg from a floor

, there can be two cases (1) The egg breaks (2) The egg doesn't break.xfloor, then we only need to check for floors lower thanxthwith remaining eggs; so the problem reduces toxfloors andx-1n-1eggs.floor, then we only need to check for floors higher thanxth; so the problem reduces toxfloors andk-xeggs.nSince 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.

Pseudo Code:C++ Implementation:OutputThe time complexity for the above approach is exponential hence it is valid only for a smaller number of inputs.

2) Dynamic Programming ApproachHere will declare the state of our dynamic programming as

wheredp[n][k]is the number of eggs we have andnis the floor we have at any instant of the moment.kThere are base cases,

dp[0][i]=0if there is no egg then simply the answer is 0.dp[1][i]=iif 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 Approachpseudo code:C++ Implementation:OutputTime 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 ApproachPseudo Code:C++ Implementation:OutputTime Complexity for the above approach is

O(n*k^2).Space Complexity for the above approach is

need an explanation for this answer? contact us directly to get an explanation for this answerO(nk).