GFG POTD: Egg dropping puzzle solution (Dynamic Programming)

Problem Statement

You are given N identical eggs and you have access to a K-floored building from 1 to K.

There exists a floor f where 0 <= f <= such that any egg dropped at a floor higher than f will break, and any egg dropped at or below floor will not break. There are few rules given below. 

  • 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 the egg doesn’t break at a certain floor, it will not break at any floor below.
  • If the eggs breaks at a certain floor, it will break at any floor above.

Return the minimum number of moves that you need to determine with certainty what the value of f is.

Example 1:

Input:
N = 1, K = 2
Output: 2
Explanation: 
1. Drop the egg from floor 1. If it 
   breaks, we know that f = 0.
2. Otherwise, drop the egg from floor 2.
   If it breaks, we know that f = 1.
3. If it does not break, then we know f = 2.
4. Hence, we need at minimum 2 moves to
   determine with certainty what the value of f is.

Example 2:

Input:
N = 2, K = 10
Output: 4

Your Task:
Complete the function eggDrop() which takes two positive integer N and K as input parameters and returns the minimum number of attempts you need in order to find the critical floor.

Expected Time Complexity : O(N*(K^2))
Expected Auxiliary Space: O(N*K)

Constraints:
1<=N<=200
1<=K<=200

Solution

int dp[202][202]; //Creating matrix of size 202*202
class Solution
{
    public:
    //Function to find minimum number of attempts needed in 
    //order to find the critical floor.
    
    //optimize the worst case
    //best of worst case
    
    int solve(int e, int f){
        
        if(f==1||f==0||e==1)
        return f;
        if(dp[e][f]!=-1) return dp[e][f];
        int minMoves=INT_MAX;
        
        for(int k=1; k<=f; k++){
            int broke=1+solve(e-1,k-1);
            int unbroke=1+solve(e,f-k);
            
            int temp=max(broke,unbroke);
            minMoves = min(minMoves, temp);
        }
        return dp[e][f]=minMoves;
        
    }
    
    int eggDrop(int n, int k) 
    {
        memset(dp,-1,sizeof(dp)); //initializing matrix with -1
        return solve(n,k);
    }
};
Write for us
GeekyBeginners articles are written by software geeks like you. If you also would like to contribute to GeekyBeginners by writing paid articles, you can check the write for us page.

Leave a Comment