## 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** <= **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**. 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= 2Output:2Explanation: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 = 10Output: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**page.