Egg Dropping Puzzle

f -> no. of floors.
e -> no. of eggs.

n (e, f) => Minimum no. of trails needed to figure out from which floor the egg will break.

Consider 6 floor building.
If egg will be dropped from 4th floor, egg will break. If drop egg from higher ie above 4th floor egg will break.
If it will not break 3rd floor, it is not breaking (lower) any below floors.

We need to find minimum trails of this.

If we drop from Kth floor, two things will happen.
i. If egg break
ii. If egg does not break

Kth floor
Egg break (e-1, k-1)
Egg does not break (e, f-k)

Kth …. like 1,2,3,4…6th floor.

Note:
+1 is already completed trail one. So, we added 1 in the break / does not break list will add.

Step : 1
This is for k =1,
(e-1,k-1) -> (1,0)
(e, f-k) ->(2,1) …..like that. Calculate for k=2,
K=1 K=2
e,f => 2,2 (1,0) (1,1)
(2,1) (2,0)
Max = 1 1

Among these we need to find minimum and add 1.
Minimum is 1.
1+1 =2.

n eggs, k floors

getDrops (n, k) – given n eggs and k floor building, minimum of drops to determine the floor from which egg does not break if dropped.

getDrops (n, k) = 1 + Min(x = 1,2,….k) [(drops(n-1, k-1), drops(n, k-x)]

public class FindWhichFloorEggWillBreak {

public static void main(String[] args) {

    int eggs = 3;
    int floors = 6;
    int whichFloorEggWillBreak = whichFloorEggWillBreak(eggs, floors);
    System.out.println(
            "Minimum no.of drops required with " + eggs + " floors " + floors + " is : " + whichFloorEggWillBreak);
}

public static int whichFloorEggWillBreak(int e, int f) {

    if (f == 0 || f == 1) {
        return f;
    }

    if (e == 1) {
        return f;
    }

    int minDrops = Integer.MAX_VALUE, tempResult;

    for (int i = 1; i <= f; i++) {
        tempResult = Math.max(whichFloorEggWillBreak(e-1, i-1), whichFloorEggWillBreak(e, f-i));
        minDrops = Math.min(tempResult, minDrops);
    }
    return minDrops + 1;
}

}

Result: Minimum no.of drops required with 3 floors 6 is : 3