You are given **A** eggs, and you have access to a building with **B** floors from **1** to **B**.

Each egg is identical in function, and if an egg breaks, you cannot drop it again.

You know that there exists a floor **C** with **0 <= C <= B** such that any egg dropped at a floor higher than **C** will break, and any egg dropped at or below floor **C** will not break.

### Confused about your next job?

Each move, you may take an egg (if you have an unbroken one) and drop it from any floor **X** (with **1 <= X <= B**).

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

What is the minimum number of moves that you need to know with certainty what **C** is, regardless of the initial value of **C**?

**Examples:**

**Input: **A = 1, B = 2**Output:** 2**Explanation:**

- 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: ** A = 2, B = 10

**Output:** 4

## Approach 1: Brute Force(Recursion)

The basic idea is, we have to find the minimum number of attempts to find the floor i.e. above that floor the egg will break and below that floor the egg will not break

So, there are two choices

- Egg will break
- Egg will not break

For **Case 1:**

- If the egg will break from a particular floor, go further below that floor.

For **Case 2:**

- For the second case if the egg will not break from a particular floor then we have to go

above to find the threshold floor.

**Base Conditions:**

**Algorithm :**** **

- Handle the base cases, when
**floors**= 0 or 1**eggs = 1**. - Run a loop from
**1**to**K**and for each iteration, recurse for the case, if the**egg**breaks on the**Xth floor**or not and maximize it. - Also, minimize the minimum floor found so far.
- Return the minimum floor.

**Implementation of the Approach:**

### C++ Code

int max(int a, int b) { return (a > b) ? a : b; } int eggDrop(int n, int k) { if (k == 1 || k == 0) return k; if (n == 1) return k; int min = INT_MAX, x, res; for (x = 1; x <= k; x++) { res = max( eggDrop(n - 1, x - 1), eggDrop(n, k - x)); if (res < min) min = res; } return min + 1; }

### Java Code

static int eggDrop(int n, int k) { if (k == 1 || k == 0) return k; if (n == 1) return k; int min = Integer.MAX_VALUE; int x, res; for (x = 1; x <= k; x++) { res = Math.max(eggDrop(n - 1, x - 1), eggDrop(n, k - x)); if (res < min) min = res; } return min + 1; }

### Python Code

import sys def eggDrop(n, k): if k == 1 or k == 0: return k if n == 1: return k min = sys.maxsize for x in range(1, k + 1): res = max(eggDrop(n - 1, x - 1), eggDrop(n, k - x)) if res < min: min = res return min + 1

**Time Complexity:** O(2^K), where K is total floors.

**Space Complexity:** O(1), as no extra space is used

## Approach 2: Dynamic Programming(Bottom up)

If you observe clearly, in the above recursive approach, there are overlapping sub-problems.

In the above image, **E(2, 2)** is being calculated twice, which can be stored in some table and can be retrieved in **O(1)**.

Let us understand the **dynamic programming **approach with an example.

Let N = 3 and K = 6, i.e. there are **3** eggs and **6 floors**.

Considering the base cases first as described above:

The recursive equation can be defined as :

*F(N,K) = **1+min{max( F(N-1,K – 1) , F(N, f – K) ) , k in 1:f}*

** **Using the above equation, the following table has been filled:

**Algorithm :**** **

- Initialise an 2D array
**eggfloor**with size**(N + 1) X (K + 1)**. - Fill the first two columns of the table using the base cases as described.
- Run a loop from
**i = 2 to N**and a nested loop from**j = 2 to K**. For each**jth**iteration, run a loop from**x**from**1**till**j**:- Find the max of
**eggfloor[i – 1][x – 1]**and**eggfloor[i][j – x]**. - Minimise the value of
**eggfloor[i][j]**.

- Find the max of
- Return the value of
**eggfloor[n][k]**.

**Implementation of the Approach:**

### C++ Code

int eggDrop(int n, int k) { int eggFloor[n + 1][k + 1]; int res; int i, j, x; for (i = 1; i <= n; i++) { eggFloor[i][1] = 1; eggFloor[i][0] = 0; } for (j = 1; j <= k; j++) eggFloor[1][j] = j; for (i = 2; i <= n; i++) { for (j = 2; j <= k; j++) { eggFloor[i][j] = INT_MAX; for (x = 1; x <= j; x++) { res = 1 + max( eggFloor[i - 1][x - 1], eggFloor[i][j - x]); if (res < eggFloor[i][j]) eggFloor[i][j] = res; } } } return eggFloor[n][k]; }

### Java Code

static int eggDrop(int n, int k) { int eggFloor[][] = new int[n + 1][k + 1]; int res; int i, j, x; for (i = 1; i <= n; i++) { eggFloor[i][1] = 1; eggFloor[i][0] = 0; } for (j = 1; j <= k; j++) eggFloor[1][j] = j; for (i = 2; i <= n; i++) { for (j = 2; j <= k; j++) { eggFloor[i][j] = Integer.MAX_VALUE; for (x = 1; x <= j; x++) { res = 1 + max( eggFloor[i - 1][x - 1], eggFloor[i][j - x]); if (res < eggFloor[i][j]) eggFloor[i][j] = res; } } } return eggFloor[n][k]; }

### Python Code

INT_MAX = 32767 def eggDrop(n, k): eggFloor = [[0 for x in range(k + 1)] for x in range(n + 1)] for i in range(1, n + 1): eggFloor[i][1] = 1 eggFloor[i][0] = 0 for j in range(1, k + 1): eggFloor[1][j] = j for i in range(2, n + 1): for j in range(2, k + 1): eggFloor[i][j] = INT_MAX for x in range(1, j + 1): res = 1 + max(eggFloor[i - 1][x - 1], eggFloor[i][j - x]) if res < eggFloor[i][j]: eggFloor[i][j] = res return eggFloor[n][k]

**Time Complexity:** O(N * K^2), where N is total eggs and K is the number of floors.

**Space Complexity:** O(N*K), as dp array is used.

**Practice Questions:**

## FAQ

**What are the special cases for the egg dropping puzzle?**There are mainly two special cases for the egg dropping puzzle-- If
**K = 0 or K = 1**, the answer is**K.** - If
**N = 1,**the answer is**K.**

- If

**What is the efficient approach to solve the egg dropping puzzle?**The dynamic programming approach is the most efficient approach to solve the problem. The time complexity is O(N*K^2) and space complexity is O(N*K).