# Egg Dropping Problem

Egg Dropping Problem: Here, we are going to learn the solution of Egg Dropping Problem, this problem has been featured in coding rounds of many big tech companies such as Amazon, MorganStanley, Flipkart, etc.
Submitted by Divyansh Jaipuriyar, on April 27, 2020

Problem statement:

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.
```

Solution Approach

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.

1. If the egg breaks after dropping from xth floor, then we only need to check for floors lower than x with remaining eggs; so the problem reduces to x-1 floors and n-1 eggs.
2. If the egg doesn't break after dropping from the xth floor, then we only need to check for floors higher than x; so the problem reduces to k-x floors and n eggs.

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.

Pseudo Code:

```    k = Number of floors
n = Number of Eggs

Drop(n, k) = 	Minimum number of trials needed to find the
threshold floor in worst case.
Drop(n, k) = 	1 + min{max(Drop(n - 1, x - 1)
Drop(n, k - x)) = x in {1, 2, ..., k}}

int Drop(n,k):
if(k==0||k==1)	//if floor is either 0 or 1 then
return k;	//simply return floor return k;

if(n==1)    // if number of egg is one return number of floor
return k

if(n==0)	// if no egg is remaining then return 0
return 0;

int res=INT_MAX;  //initilise res with maximum value
int subres;	 // for calculating recursive attemps value

for(int i=1;i<=k;i++)
{
// considering wordst case thats why calculating
// the max attempt of the two.
subres=max(Drop(n-1,i-1),Drop(n,k-i));
res=min(res,1+subres)
}    // 1 is added for the current attempt

// then we pick the min of current attempts
return res
```

C++ Implementation:

```#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

ll Drop(ll n, ll k)
{
if (k == 0 || k == 1) //base cases if floor is 0 or 1
return k;
if (n == 1) // if one egg simply return floor value
return k;
if (n == 0)
return 0;
ll res = INT_MAX;
for (ll i = 1; i <= k; i++) {
// max is taken because of worst case
ll subres = max(Drop(n - 1, i - 1), Drop(n, k - i));
// one is added because of current attempt
res = min(res, 1 + subres);
}
return res; // return result.
}

int main()
{
ll t;

cout << "Enter number of test cases: ";
cin >> t;

while (t--) {
cout << "Enter number of eggs and floors: ";
ll n, k;
cin >> n >> k;

cout << "Minimum number of attempts: ";
cout << Drop(n, k) << "\n";
}
return 0;
}
```

Output

```Enter number of test cases: 3
Enter number of eggs and floors: 2 5
Minimum number of attempts: 3
Enter number of eggs and floors: 2 10
Minimum number of attempts: 4
Enter number of eggs and floors: 3 8
Minimum number of attempts: 4
```

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

pseudo code:

```int Drop(n,k):
{
// base cases if floor is 0 or 1
if(k==0||k==1)
return k

// if there is no eggs the reuturn 0
if(n==0)
return 0

// if it iw calculate already then smiply return
if(dp[n][k]!=-1)
return dp[n][k]

// temporarly declare the max value of result
int res=INT_MAX

for(int i=1;i<=k;i++)
{
// find the max of the two cases
int subres=max(Drop(n-1,i-1),Drop(n,k-i))
// 1 is added for current floor attempt
res=min(res,1+subres)
}
dp[n][k]=res;
return dp[n][k]
}
```

C++ Implementation:

```#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
ll dp;

ll Drop(ll n, ll k)
{
if (k == 0 || k == 1) // base cases
return k;
if (n <= 0) //no eggs simply return 0
return 0;
if (dp[n][k] != -1) // memoized value return
return dp[n][k];
ll ans = INT_MAX;
for (ll i = 1; i <= k; i++) {
// maximum value for worst case condition
ll subres = max(Drop(n - 1, i - 1), Drop(n, k - i));
ans = min(ans, subres);
}
// one is added for current attempt
dp[n][k] = 1 + ans;
return dp[n][k];
}

int main()
{
ll t;
cout << "Enter number of test cases: ";
cin >> t;

while (t--) {
cout << "Enter number of eggs and floors: ";
ll n, k;
cin >> n >> k;

for (ll i = 0; i <= n; i++)
for (ll j = 0; j <= k; j++)
dp[i][j] = -1;

dp = 0;

for (ll i = 1; i <= k; i++) {
dp[i] = 0;
dp[i] = i;
}

ll res = Drop(n, k);

cout << "Minimum number of attempts: ";
cout << res << "\n";
}
return 0;
}
```

Output

```Enter number of test cases: 4
Enter number of eggs and floors: 2 10
Minimum number of attempts: 4
Enter number of eggs and floors: 2 100
Minimum number of attempts: 14
Enter number of eggs and floors: 2 36
Minimum number of attempts: 8
Enter number of eggs and floors: 2 1
Minimum number of attempts: 1
```

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

Pseudo Code:

```int Drop(int n, int k)
{
/* A 2D table where entery dp[i][j] will represent minimum
number of attempts needed for i eggs and j floors. */
int dp[n+1][k+1];
int res;
int i, j, x;

// We need one attempts for one floor and 0 attemts for 0 floors
for (i = 1; i <= n; i++)
{
dp[i] = 1;
dp[i] = 0;
}

// We always need j attempts for one egg and j floors.
for (j = 1; j <= k; j++)
dp[j] = j;

// Fill rest of the entries in table using optimal substructure
// property
for (i = 2; i <= n; i++)
{
for (j = 2; j <= k; j++)
{
dp[i][j] = INT_MAX;
for (x = 1; x <= j; x++)
{
// worst case condition
res =max(dp[i-1][x-1], dp[i][j-x]);
if (res < dp[i][j])
// plus one for current attempt
dp[i][j] = res+1;
}
}
}

// dp[n][k] holds the result
return dp[n][k];
}
```

C++ Implementation:

```#include <bits/stdc++.h>
using namespace std;

int main()
{
int t;
cout << "Enter number of test cases: ";
cin >> t;

while (t--) {
int n, k;

cout << "Enter number of eggs and number of floors: ";
cin >> n >> k;

int dp[n + 1][k + 1];
memset(dp, 0, sizeof(dp));
dp = 0; //if we have 0 eggs
dp = 0;

for (int i = 1; i <= n; i++) {
dp[i] = 0;
dp[i] = 1;
} // when we have 0 or 1 floor then we need 0 and one
// attempts in worst case respectively

for (int i = 1; i <= k; i++) {
dp[i] = 0, dp[i] = i;
} //base cases

for (int i = 2; i <= n; i++) {
for (int j = 2; j <= k; j++) {
dp[i][j] = INT_MAX;
for (int x = 1; x <= j; x++) {
// max for worst case
int subres = max(dp[i - 1][x - 1], dp[i][j - x]);
// one added for current attempts.
dp[i][j] = min(dp[i][j], 1 + subres);
}
}
}

cout << "Minimum number of attempts: ";
cout << dp[n][k] << "\n";
}

return 0;
}
```

Output

```Enter number of test cases: 3
Enter number of eggs and number of floors: 2 10
Minimum number of attempts: 4
Enter number of eggs and number of floors: 2 100
Minimum number of attempts: 14
Enter number of eggs and number of floors: 4 6
Minimum number of attempts: 2
```

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

Space Complexity for the above approach is O(nk).

Problem reference: https://www.codechef.com/problems/CODEY202