How many floors can an egg be dropped without breaking?

Question: You have two identical eggs. Standing in front of a 100 floor building, you wonder what is the maximum number of floors from which the egg can be dropped without breaking it. What is the minimum number of tries needed to find out the solution?

Answer: The easiest way to do this would be to start from the first floor and drop the egg. If it doesn’t break, move on to the next floor. If it does break, then we know the maximum floor the egg will survive is 0. If we continue this process, we will easily find out the maximum floors the egg will survive with just one egg. So the maximum number of tries is 100 that is when the egg survives even at the 100th floor.

Can we do better? Of course we can. Let’s start at the second floor. If the egg breaks, then we can use the second egg to go back to the first floor and try again. If it does not break, then we can go ahead and try on the 4th floor (in multiples of 2). If it ever breaks, say at floor x, then we know it survived floor x-2. That leaves us with just floor x-1 to try with the second egg. So what is the maximum number of tries possible? It occurs when the egg survives 98 or 99 floors. It will take 50 tries to reach floor 100 and one more egg to try on the 99th floor so the total is 51 tries. Wow, that is almost half of what we had last time.

Can we do even better? Yes we can (Bob, the builder). What if we try at intervals of 3? Applying the same logic as the previous case, we need a max of 35 tries to find out the information (33 tries to reach 99th floor and 2 more on 97th and 98th floor).

Interval – Maximum tries
1 – 100
2 – 51
3 – 35
4 – 29
5 – 25
6 – 21
7 – 20
8 – 19
9 – 19
10 – 19
11 – 19
12 – 19
13 – 19
14 – 20
15 – 20
16 – 21

So picking any one of the intervals with 19 maximum tries would be fine.

Update: Thanks to RiderOfGiraffes for this solution.

Instead of taking equal intervals, we can increase the number of floors by one less than the previous increment. For example, let’s first try at floor 14. If it breaks, then we need 13 more tries to find the solution. If it doesn’t break, then we should try floor 27 (14 + 13). If it breaks, we need 12 more tries to find the solution. So the initial 2 tries plus the additional 12 tries would still be 14 tries in total. If it doesn’t break, we can try 39 (27 + 12) and so on. Using 14 as the initial floor, we can reach up to floor 105 (14 + 13 + 12 + … + 1) before we need more than 14 tries. Since we only need to cover 100 floors, 14 tries is sufficient to find the solution.

Therefore, 14 is the least number of tries to find out the solution.

via www.mytechinterviews.com

💡Strategies for Solving This Problem

The Egg Drop Problem

Classic DP problem that showed up at Microsoft in 2023. It's about minimizing worst-case attempts, not average case. That trips people up.

The Problem

You have k eggs and a building with n floors. Find the minimum number of drops needed to find the critical floor (highest floor from which an egg won't break) in the worst case.

Understanding the Problem

Key constraints:

If an egg breaks, you can't reuse it
If it doesn't break, you can drop it again
Need to find the threshold floor
Minimize worst-case drops, not average

Approach 1: Two Eggs, Linear Scan

With 2 eggs and 100 floors, you might think: drop from floor 10, 20, 30... If it breaks at 30, go back and try 21, 22, 23...

Worst case: First egg breaks at 100 (10 drops), then 9 more drops. Total: 19 drops.

But we can do better.

Approach 2: Two Eggs, Optimal

Use decreasing intervals! Start at floor 14. If it breaks, check floors 1-13 (13 drops). If it doesn't break, go to floor 27 (14+13). If it breaks there, check floors 15-26 (12 drops).

Pattern: 14, 27, 39, 50, 60, 69, 77, 84, 90, 95, 99, 100

Worst case: 14 drops for 100 floors.

Why? First drop + remaining floors should equal worst case constant.

General Solution: Dynamic Programming

For k eggs and n floors, use DP:

dp[k][n] = minimum drops needed with k eggs and n floors

Recurrence:

dp[k][n] = 1 + min(
    max(dp[k-1][x-1], dp[k][n-x])
) for all x from 1 to n

If we drop from floor x:

Egg breaks: Check floors 1 to x-1 with k-1 eggs
Egg survives: Check floors x+1 to n with k eggs
Take max (worst case), minimize over all x

At Microsoft

Started with the 2-egg solution. Interviewer asked "What if you have unlimited eggs?" Answer: Binary search, log n drops. Then asked for general solution - that's when I pulled out DP.

✅Solution

Solution: Dynamic Programming

function eggDrop(eggs, floors) {
    // dp[k][n] = min drops with k eggs and n floors
    const dp = Array(eggs + 1).fill(null)
        .map(() => Array(floors + 1).fill(0));

    // Base cases
    // With 1 egg, need linear search
    for (let n = 1; n <= floors; n++) {
        dp[1][n] = n;
    }

    // With 0 or 1 floor, need at most 1 or 0 drops
    for (let k = 1; k <= eggs; k++) {
        dp[k][0] = 0;
        dp[k][1] = 1;
    }

    // Fill dp table
    for (let k = 2; k <= eggs; k++) {
        for (let n = 2; n <= floors; n++) {
            dp[k][n] = Infinity;

            // Try dropping from each floor
            for (let x = 1; x <= n; x++) {
                // Breaks: check floors below with k-1 eggs
                // Survives: check floors above with k eggs
                const worstCase = 1 + Math.max(
                    dp[k - 1][x - 1],  // Breaks
                    dp[k][n - x]       // Survives
                );

                dp[k][n] = Math.min(dp[k][n], worstCase);
            }
        }
    }

    return dp[eggs][floors];
}

// Tests
console.log(eggDrop(2, 10));   // 4
console.log(eggDrop(2, 100));  // 14
console.log(eggDrop(3, 14));   // 4
console.log(eggDrop(1, 10));   // 10 (linear search)

Optimized: Binary Search on Floors

The inner loop can use binary search because dp[k-1][x-1] increases and dp[k][n-x] decreases as x increases. Find the crossover point.

function eggDropOptimized(eggs, floors) {
    const dp = Array(eggs + 1).fill(null)
        .map(() => Array(floors + 1).fill(0));

    // Base cases
    for (let n = 1; n <= floors; n++) {
        dp[1][n] = n;
    }
    for (let k = 1; k <= eggs; k++) {
        dp[k][0] = 0;
        dp[k][1] = 1;
    }

    // Fill dp table with binary search
    for (let k = 2; k <= eggs; k++) {
        for (let n = 2; n <= floors; n++) {
            let left = 1, right = n;
            dp[k][n] = Infinity;

            while (left <= right) {
                const mid = Math.floor((left + right) / 2);

                const breaks = dp[k - 1][mid - 1];
                const survives = dp[k][n - mid];

                const worstCase = 1 + Math.max(breaks, survives);
                dp[k][n] = Math.min(dp[k][n], worstCase);

                if (breaks > survives) {
                    right = mid - 1;  // Try lower floors
                } else {
                    left = mid + 1;   // Try higher floors
                }
            }
        }
    }

    return dp[eggs][floors];
}

console.log(eggDropOptimized(2, 100));  // 14

Two Eggs, Closed Form

For exactly 2 eggs, there's a formula:

function twoEggs(floors) {
    // Find smallest n where n*(n+1)/2 >= floors
    // This is solving: n + (n-1) + (n-2) + ... + 1 >= floors
    let n = 1;
    while (n * (n + 1) / 2 < floors) {
        n++;
    }
    return n;
}

console.log(twoEggs(100));  // 14
console.log(twoEggs(10));   // 4

Why This Works

For 2 eggs with optimal strategy:

Drop 1: floor n (if breaks, need n-1 more drops)
Drop 2: floor n + (n-1) (if breaks, need n-2 more drops)
Drop 3: floor n + (n-1) + (n-2)
...

Total floors covered: n + (n-1) + (n-2) + ... + 1 = n*(n+1)/2

We need n*(n+1)/2 >= floors, so solve for n.

Special Cases

Unlimited eggs: Binary search, O(log n) drops

function unlimitedEggs(floors) {
    return Math.ceil(Math.log2(floors + 1));
}

console.log(unlimitedEggs(100));  // 7

One egg: Must check linearly, n drops

Complexity Analysis

Solution	Time	Space
DP basic	O(k × n²)	O(k × n)
DP optimized	O(k × n × log n)	O(k × n)
2 eggs formula	O(√n)	O(1)

Step-by-Step Example: 2 Eggs, 10 Floors

dp[2][10]:

Try x=1: max(dp[1][0], dp[2][9]) = max(0, ?) - need dp[2][9]
Try x=4: max(dp[1][3], dp[2][6]) = max(3, ?)
...

Building from smaller problems:
dp[2][1] = 1
dp[2][2] = 2
dp[2][3] = 2 (drop from floor 2)
dp[2][4] = 3 (drop from floor 2 or 3)
...
dp[2][10] = 4

Optimal strategy: Drop from floors 4, 7, 9, 10

Common Mistakes

Minimizing average case: Problem asks for worst case
Not considering both outcomes: Must handle break and survive
Off-by-one errors: Be careful with floor counting
Forgetting egg limit: Can't just binary search if you run out of eggs

Follow-Up Questions

Q: With unlimited eggs?
A: Binary search, O(log n) drops

Q: With 1 egg?
A: Linear search from bottom, n drops

Q: Find the actual floor sequence?
A: Track which floor x gave optimal result in DP, backtrack