Drop Eggs

Question I (LI.254)

There is an egg museum that has 100 floors. Each floor stores a historical egg. Higher floors store more expensive eggs. The thief gets 2 replica eggs from the gift shop. What is the minimum number of drops in order to find the right floor to steal the egg?

Example

I: n = 100
O: 14

Analysis

If there's only one egg, then we don't have much to do. The only approach would be trying it in every floor until it breaks. Having a second egg will give the thief more options. One approach can be dropping the first egg in a set interval. For example, every 10 floors. Then dropping the second egg at the interval before the first egg breaks. The worst case will be 19 for this approach. We want to optimize the number of tries in the worse case. Mathematically, this can be expressed as the following inequality $n + (n-1) + (n-2) + (n-3) + (n-4) + ... + 1 \geq 100$.

Code

Solving this inequality by summation.

public int dropEggs(int n) {
    int floor = 0;
    long sum = 0;
    while (sum < n) {
        floor++;
        sum += floor;
    }
    return floor;
}

Question II (LI.584)

The building still has n floors. But now we are given m replica eggs instead of 2. What is the minimum number of drops in the worst case?

Example

(100, 2) => 14
(36, 2) => 8

Analysis

References

Ted Ed - Egg Drop Riddle