# Egg Dropping Puzzle

### Egg Dropping Puzzle

##### We need to find minimum number of egg droppings that will work in all cases (including worst-case).

Formula:

• This problem is not above from which floor eggs should be dropped, its about to minimize number of drops.
• Suppose, we have n eggs and k floors then,
• Base Case:
• `When floor is 1 then, MinNoOfDrops(n, 1) = 1`
• `And, when egg is 1 the, MinNoOfDrops(1, k)=k`
• Generailsed Solution:
• `MinNoOfDrops(n, k) = 1 + min{ max(MinNoOfDrops(n − 1, x − 1), MinNoOfDrops(n,k − x)) } , x = 1, 2, ..., k`
##### Dynamic Programming Algorithm:
1. Create dp `table of (totalEggs + 1) X (totalFloors + 1)`
2. Base Case: When egg is zero or one then, set for floor i, `table[i] = 0; and table[i] = i`
3. Base Case: Floor is zero or one then, set for egg j,` table[j] = 0 and table[j] = 1`
4. Iterate egg i from 2 to total_eggs
1. Iterate floor j from 2 to total_floors
2. Set `table[i][j] = INFINITY`
3. Iterate floor k from 1 to j
1. Set maxDrop = 1 + max(table[i-1][k-1], table[i][j-k])
2. If `table[i][j] > maxDrop` then
1. `table[i][j] = maxDrop`
5. `return table[totalEggs][totalFloors]`

Latest Source Code:
Github: EggDroppingPuzzle.java

Output:

```Total Floors : 10
Total Eggs : 2
Minimum Drops (By DP): 4
Minimum Drops (By recursion): 4
```
Author: