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[0][i] = 0; and table[1][i] = i
3. Base Case: Floor is zero or one then, set for egg j, table[j][0] = 0 and table[j][1] = 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

Wiki

StackOverFlow

Quora