Egg dropping puzzle

I started writing blogs to help people like me who think why it is happening in that way. This blog also follows the same motto but for now, it follows in a dynamic programming problem

Problem statement :

Given N floors and K eggs, the minimum number of attempts required to find in which floor the egg will break?

Some assumptions are needed to solve this -
1. you can use the unbroken egg for next attempt
2. you need to discard the egg which is broken
3. you need to consider that egg may break from first floor or egg may not break even from Nth floor
4. you need to consider that all eggs will have same strength
5. If an egg doesn’t break on floor X, it won’t break from 1 to X-1 floors

Let’s go to “How to” section now:

Let’s say you have 1 egg and 0 floors -> here you can find the number of attempts as 0.
Let’s say you have 1 egg and 5 floors -> here you have the number of attempts as the Xth floor since you only have one egg you need to go to every floor and test until your egg is broken.
Let’s say you have 0 eggs and N floors -> pretty simple right, 0 as you have nothing to perform anything

Had enough initial conditions, let's dive into the nucleus now:
The approach is for finding the minimum number of attempts required to tell in which floor the egg may break you need to calculate the number of attempts it may take for k eggs, from each floor.

analogy: for every floor, you have two simple cases -
1. The egg may break- then you will have (X-1 floors and k-1 eggs) to deal
2. The egg may not break- then you will have (N-X floors and k eggs) to deal

So the desired equation will be
minAttempts( N , K) = 1 + min( max( minAttempts(X-1, K-1), minAttempts(N-X, k)
for X = 1 to N

we add plus one to consider the current attempt and min for getting minimum number of attempts while trying from each individual floor and max to consider the egg won’t break scenario, else we may end up considering only egg break scenarios

so the above equation if implemented in recursion it looks in this fashion

if(eggs == 1){             
   return floors;
 }
if(floors == 0){
    return 0; 
 } 
int min = INT_MAX;
for(int i=1; i <= floors; i++){      
    int val = 1 + Math.max(calculateRecursive(eggs-1, i-1),calculateRecursive(eggs, floors-i));
    if(val < min){
        min = val; 
     }  
   } 
 return min;

But you can observe many redundant calls being made if you debug line by line, for that reason you can opt for a Dynamic Programming Solution instead, where you can store the calculated values in a buffer and use those instead of calculating again.

Let us go through the DP solution:
let's take a buffer — T[eggs + 1][floors + 1]
The additional buffer is needed to use for zero floors and zero eggs case

Now with one egg, the number of attempts needed to find if egg breaks or not will be the number of floors since you need to go to the floor every floor and test until the egg breaks. So we can fill the buffer initially in this way

for f = 0 to number_of_floors:
   T[1][f] = f 

Now for remaining eggs:
As discussed above go to each floor and find out the number of attempts required to break through that floor and take the minimum of that.

attempts_through_each_floor = 0
for egg = 2 to number_of_eggs:
  for floor = 1 to number_of_floors:
    T[egg][floor] = INT_MAX
    for k = 1 to floor:
      attempts_through_each_floor = 1 + max(T[egg-1][floor-1], T[egg][number_of_floors - k])
     if T[egg][floor] < attempts_through_each_floor:
       T[egg][floor] = attempts_through_each_floor
#if you are not using java then initialize matrix with zeroes

In this way, the number in the final block of the matrix gives you the desired solution. Hope this helps in you understanding the problem