Today we will be talking about a very famous interview problem which is as follows:

Given a certain amount of floors of a building (say k number of floors) and also given certain amount of eggs (say n number of eggs) …

What is the least amount of egg drops one has to perform to find out the threshold floor? (Threshold floor is one from which the egg starts breaking and also egg breaks for all the floors above. Also, if egg dropped from any floor below the threshold floor, it will not break.)

Constraints:

  • An egg that survives a fall can be used again.
  • A broken egg must be discarded.
  • The effect of a fall is the same for all eggs.
  • If an egg breaks when dropped, then it would break if dropped from a higher floor.
  • If an egg survives a fall then it would survive a shorter fall.

One thing is to be remembered that we are finding the least amount of egg drops needed to find threshold and not the threshold floor itself.

This problem is called the Egg Dropping Problem.

For example:
Input:
Number of eggs = 2
Number of floors = 10

Output:
4

To solve this problem, lets do some observation

Initially we have n number of eggs and k number of floors, if we drop an egg from a floor x then we have two cases:

  1. If the egg breaks, then the threshold floor must be lower than x. So now we are left with n-1 eggs and x-1 floors to check.
  2. If the egg doesn’t break then the threshold floor must be higher than x, So now we have n eggs and k-x floors to check.

As we have to minimize the drops in the worst case, we will take the maximum of the two cases.

Our final answer is going to be the minimum for all the values of x from 1 to k.

In a nutshell we can say

If solve( n , k ) represents the minimum number of drops for n number of eggs and k number of floors, then

solve( n , k ) = 1 + max( solve( n -1 ,  x-1 ), solve( n , k-x ) )

for every x in range 1 to k.

Base case:

  1. If we have only one egg then the only option we have is to drop the egg from each floor from lower to higher.
    solve( 1 , k ) =k.
  2. If the number of floors left are zero then that means we have found our threshold floor,So we don’t need to do more drops.
    solve( n , 0 ) = 0.

Here is the code:

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

int solve(int n, int k)
{
	if (n == 1 or k == 0) // Base case
	{
		return k;
	}
	int ans = INT_MAX;
	for (int i = 1; i<= k; i++)
	{
		ans = min(ans, 1 + max(solve(n - 1, i - 1), solve(n, k - i)));
	}
	return ans;
}
int main()
{
	int n, k;
	cin>> n >>k;
	int ans = solve(n, k);
	cout<<ans<<endl;
	return 0;
}

The time complexity of this solution is exponential which is not good.

Let’s try to solve it using dynamic programming.

Overlapping substructure

As I have already explained above, this problem has overlapping substructure

solve( n , k ) = 1 + max( solve( n -1 ,  x-1 ), solve( n , k-x ) )

for every x in range 1 to k.

Overlapping subproblem

Let’s draw the recursion tree

For instance take n=2 and k=3.

As a state, say solve(2,1) is calculated more than once and there are many states which are being calculated again and again. So, this problem also has overlapping subproblem property.

This problem has both the properties needed to solve it using dynamic programming.

We will store our answer for a state so it won’t be recomputed.

Dp[ i ][ j ] stores the best answer when we have i number of eggs and j number of floors.

Base case is same as for recursive solution:

  1. Dp( 1 , k ) = k.
  2. Dp( n , 0 ) = 0.

Here is the code for top-down DP:

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

int solve(int n, int k, vector<vector<int>>&dp)
{
	if (dp[n][k] != -1)   // checking we are not recomputing the same state again
	{
		return dp[n][k];
	}
	if (n == 1 or k == 0) // Base case
	{
		return k;
	}
	int ans = INT_MAX;
	for (int i = 1; i<= k; i++)
	{
		ans = min(ans, 1 + max(solve(n - 1, i - 1, dp), solve(n, k - i, dp)));
	}
	dp[n][k] = ans;       //Updating our DP array
	return dp[n][k];
}
int main()
{

	int n, k;
	cin>> n >>k;
	vector<vector<int>>dp(n + 1, vector<int>(k + 1, -1));
	int ans = solve(n, k, dp);
	cout<<ans<<endl;

	return 0;
}

Here is the code for bottom up DP:

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

int solve(int n, int k, vector<vector<int>>&dp)
{
	for (int i = 0; i<= k; i++)
	{
		dp[1][i] = i;
	}
	for (int i = 0; i<= n; i++)
	{
		dp[i][0] = 0;
		dp[i][1] = 1;
	}
	for (int i = 2; i<= n; i++)
	{
		for (int j = 2; j <= k; j++)
		{
			dp[i][j] = INT_MAX;
			int res;
			for (int x = 1; x <= j; x++)
			{
				res = 1 + max(dp[i - 1][x - 1], dp[i][j - x]);
				if (res <dp[i][j])
					dp[i][j] = res;
			}
		}
	}
	return dp[n][k];
}
int main()
{
	int n, k;
	cin>> n >>k;
	vector<vector<int>>dp(n + 1, vector<int>(k + 1, INT_MAX));
	int ans = solve(n, k, dp);
	cout<<ans<<endl;
	return 0;
}
Input:
2 10
Output:
4

By using dynamic programming, we have reduced the time complexity from exponential to O(n*k*k) which is a big improvement.

Also, I recommend to solve DP problems using top down approach as it is more intuitive and less prone to mistakes.

Thank you Shiva Gupta for this article.


1 Comment

Anikash · May 5, 2020 at 6:17 am

Amazing

Leave a Reply

Your email address will not be published. Required fields are marked *

Insert math as
Block
Inline
Additional settings
Formula color
Text color
#333333
Type math using LaTeX
Preview
\({}\)
Nothing to preview
Insert