Egg Dropping Puzzle

The Egg Dropping Puzzle is a classic problem: Given n eggs and a building with k floors, find the minimum number of egg drops needed in the worst-case scenario to find the highest floor from which an egg can be dropped without breaking (the threshold floor).

Assumptions & Rules

An egg that survives a fall can be used again.
A broken egg must be discarded.
The effect of a fall is the same for all eggs.
If an egg breaks when dropped, it would break if dropped from a higher floor.
If an egg survives a fall, it would survive a fall from a lower floor.
It is possible that the first-floor window breaks eggs, or even the highest floor does not break eggs.

Optimal Substructure

When we drop an egg from floor x (where 1 <= x <= k), there are two possible outcomes:

The egg breaks: The problem reduces to x - 1 floors and n - 1 eggs (we must check the floors below x).
The egg does not break: The problem reduces to k - x floors and n eggs (we must check the floors above x).

To guarantee a result in the worst case, we take the maximum of these two outcomes. Since we want to choose the floor x that minimizes this worst-case number of drops, the recurrence relation is:

eggDrop(n, k) = 1 + min( max(eggDrop(n-1, x-1), eggDrop(n, k-x)) ) for all 1 <= x <= k

Base Cases

eggDrop(n, 0) = 0 (0 floors -> 0 trials needed).
eggDrop(n, 1) = 1 (1 floor -> 1 trial needed).
eggDrop(1, k) = k (1 egg -> must test all k floors sequentially from bottom to top).

1. Recursive Solution (Naive)

This naive solution has an exponential time complexity due to overlapping subproblems.

function eggDropRecursive(n, k) {
    // If there are no floors or 1 floor
    if (k === 1 || k === 0) return k;
 
    // We need k trials for 1 egg and k floors
    if (n === 1) return k;
 
    let min = Infinity;
 
    // Consider all drops from 1st floor to kth floor
    for (let x = 1; x <= k; x++) {
        const res = Math.max(
            eggDropRecursive(n - 1, x - 1),
            eggDropRecursive(n, k - x)
        );
        if (res < min) {
            min = res;
        }
    }
 
    return min + 1;
}

2. Memoization Solution (Top-Down DP)

function eggDropMemoization(n, k) {
    const memo = Array.from({ length: n + 1 }, () => new Array(k + 1).fill(-1));
 
    function helper(eggs, floors) {
        if (floors === 1 || floors === 0) return floors;
        if (eggs === 1) return floors;
 
        if (memo[eggs][floors] !== -1) return memo[eggs][floors];
 
        let min = Infinity;
 
        for (let x = 1; x <= floors; x++) {
            const res = Math.max(
                helper(eggs - 1, x - 1),
                helper(eggs, floors - x)
            );
            if (res < min) {
                min = res;
            }
        }
 
        memo[eggs][floors] = min + 1;
        return memo[eggs][floors];
    }
 
    return helper(n, k);
}

3. Tabulation Solution (Bottom-Up DP)

We construct a 2D table dp of size (n+1) x (k+1).

function eggDropTabulation(n, k) {
    const dp = Array.from({ length: n + 1 }, () => new Array(k + 1).fill(0));
 
    // Base cases: 1 trial for 1 floor, 0 trials for 0 floors
    for (let i = 1; i <= n; i++) {
        dp[i][1] = 1;
        dp[i][0] = 0;
    }
 
    // Base case: i trials for i floors with 1 egg
    for (let j = 1; j <= k; j++) {
        dp[1][j] = j;
    }
 
    // Fill the rest of the table using the recurrence relation
    for (let i = 2; i <= n; i++) {
        for (let j = 2; j <= k; j++) {
            dp[i][j] = Infinity;
            for (let x = 1; x <= j; x++) {
                const res = 1 + Math.max(dp[i - 1][x - 1], dp[i][j - x]);
                if (res < dp[i][j]) {
                    dp[i][j] = res;
                }
            }
        }
    }
 
    return dp[n][k];
}
 
// Driver code
const eggs = 2;
const floors = 10;
console.log(`Min trials in worst case with ${eggs} eggs and ${floors} floors is:`, eggDropTabulation(eggs, floors));
// Output: Min trials in worst case with 2 eggs and 10 floors is: 4

Complexity Analysis

Time Complexity: O(N * K^2)
- There are N * K states in the DP table, and for each state, we iterate up to K times to find the optimal floor x.
Space Complexity: O(N * K)
- To store the 2D DP table.

Optimal Strategy for a Game Count BSTs with n keys