Home » Interview coding problems/challenges

# 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

*floors from*

**K***to*

**1***. 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*

**K***with*

**F***such that any egg dropped at a floor higher than*

**0 <= F <= K***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*

**F***(with*

**X***). Your goal is to know with certainty what the value of*

**1 <= X <= K***is.*

**F**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

*test cases follow. Each test case contains one line denoting*

**T***number of eggs and*

**N***denoting*

**K***number of floors.*

**K**### 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).

## Explanation with example

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.

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

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

*is the number of eggs we have and*

**n***is the floor we have at any instant of the moment.*

**k**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

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

Comments and Discussions!