Egg Dropping Puzzle (DP-18)

You are given n number of eggs and you have K floors. You need to find out the minimum number of trials in worst case to find out the lowest floor from which if an egg is dropped, it breaks. Assume that, if in any of the trials, an egg breaks, it can’t be used for further trials.

Sample Input: N=2, K=36
Expected Output: 8
Explanation: You need 8 trials in the worst case to find the lowest floor from which if an egg is dropped, it breaks.

Algorithm:

The problem can be solved using Dynamic Programming because it has both optimal substructure and overlapping sub problems.

  1. We create a 2D array DP store the results of the sub problems. The size of the array is (n+1, k+1).
  2. If n=1 which means if we have 1 egg, we need i trials (0<=i<=K).
  3. If K=0, we need 0 trials and if K=1, we need 1 trials irrespective of the number of eggs we have.
  4. When we drop an egg from a floor x, there can be two scenarios, the egg breaks or it does not break.
    If the egg breaks, then we only need to check for floors which are lower then x with remaining number of eggs. Thus the sub problem reduces to (N-1, X-1).
    If the egg does not break, then we only need to check for higher floors. Thus the problem reduces to (N, K-x).
#include <bits/stdc++.h>
using namespace std;

int helper(int n, int k){
	vector<vector<int>> dp(n+1, vector<int>(k+1, INT_MAX));
	for(int i = 0; i<=n; i++){
		dp[i][0] = 0;
		dp[i][1] = 1;
	}
	for(int i=2; i<=k; i++){
		dp[1][i] = i;
	}
	for(int i=2; i<=n; i++){
		for(int j=2; j<=k; j++){
			for(int x = 1; x<=j; x++){
				int res = 1 + max(dp[i-1][x-1], dp[i][j-x]);
				dp[i][j] = min(res, dp[i][j]);
			}
		}
	}
	return dp[n][k];
}

int main(){
	int n=2, k=36;
	cout<<helper(n, k);
	return 0;
}

Also, check out another popular interview problem Number of ways to reach N’th stair.

2 comments

Leave a Reply

Your email address will not be published.