Q:

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

mahmoud2506
Save to bookmark
|
2022-05-01
|
  266 
0

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.
C++ programming, Interview questions, C++ programming Interview-questions,
login and add your own answer to this question

All Answers

mahmoud2506
2022-05-01
need an explanation for this answer? contact us directly to get an explanation for this answer

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[0][i]=0 if there is no egg then simply the answer is 0.
dp[1][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[1004][1004];

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][0] = 0;

        for (ll i = 1; i <= k; i++) {
            dp[0][i] = 0;
            dp[1][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] = 1; 
		dp[i][0] = 0; 
	} 

	// We always need j attempts for one egg and j floors. 
	for (j = 1; j <= k; j++) 
		dp[1][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][0] = 0; //if we have 0 eggs
        dp[0][1] = 0;

        for (int i = 1; i <= n; i++) {
            dp[i][0] = 0;
            dp[i][1] = 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[0][i] = 0, dp[1][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

need an explanation for this answer? contact us directly to get an explanation for this answer

total answers (1)

Top C++ Dynamic programming problems for interviews
This question belongs to these collections

Similar questions

need a help?

find thousands of online teachers now
Given an array of size n and a sum K, determine wh... >>
<< Given two strings string1 and string2 find the min...