Super Egg Drop - Leetcode Solution

Problem Statement: You are given K eggs, and you have access to a building with N floors from 1 to N.

Each egg is identical in function and hardness, and if an egg breaks, it cannot be used again.

After carrying out some experiments, you have decided that the only strategy that works is to drop the eggs from the minimum floor possible (0th floor) and to move up floor by floor until the egg breaks, or it doesn't.

You are asked to find the minimum number of moves, in the worst case scenario, to determine the floor at which the eggs break.

Solution:

This problem can be solved using dynamic programming, specifically by using memoization to optimize the recursive solution.

Let us define f(K, N) as the minimum number of moves needed to determine the floor at which the egg breaks using K eggs on a building with N floors.

First, consider the scenario where we drop an egg at a certain floor x.

Case 1: Egg breaks

In this case, we have K-1 eggs left and we need to determine the minimum number of moves required to determine the floor at which the egg breaks using these K-1 eggs and the remaining floors from 1 to x-1.

Case 2: Egg doesn't break

In this case, we still have K eggs left and we need to determine the minimum number of moves required to determine the floor at which the egg breaks using these K eggs and the remaining floors from x+1 to N.

Therefore, we can define f(K, N) as follows:

f(K, N) = min(1 + max(f(K-1, x-1), f(K, N-x)))

where the minimum number of moves required to determine the floor at which the egg breaks using K eggs on a building with N floors is equal to 1 (the current floor we are dropping the egg at) plus the maximum of the moves required in Case 1 and Case 2.

The base cases are:

f(K, 0) = 0 (no floors, no moves required) f(K, 1) = 1 (one floor, one move required)

Therefore, we can use memoization to store the previously calculated values and reduce the time complexity.

Code:

int eggDrop(int k, int n) { vector<vector<int>> memo(k+1, vector<int>(n+1,-1)); return dfs(k,n,memo); }

int dfs(int k, int n, vector<vector<int>>& memo){ if(n==0||n==1) return n; if(k==1) return n; if(memo[k][n]!=-1) return memo[k][n]; int res = INT_MAX; for(int i=1;i<=n;i++){ int broken = dfs(k-1,i-1,memo); int not_broken = dfs(k,n-i,memo); int temp_res = max(broken,not_broken)+1; res = min(res,temp_res); } memo[k][n] = res; return res; }

Running time complexity: O(kn^2)

1