### 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`

- Base Case:

##### Dynamic Programming Algorithm:

- Create dp
`table of (totalEggs + 1) X (totalFloors + 1)`

- Base Case: When egg is zero or one then, set for floor i,
`table[0][i] = 0; and table[1][i] = i`

- Base Case: Floor is zero or one then, set for egg j,
`table[j][0] = 0 and table[j][1] = 1`

- Iterate egg i from 2 to total_eggs
- Iterate floor j from 2 to total_floors
- Set
`table[i][j] = INFINITY`

- Iterate floor k from 1 to j
- Set maxDrop = 1 + max(table[i-1][k-1], table[i][j-k])
- If
`table[i][j] > maxDrop`

then`table[i][j] = maxDrop`

`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