Solution For Super Egg Drop
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
return dfs(k,n,memo);
}
int dfs(int k, int n, vector
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)
Step by Step Implementation For Super Egg Drop
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 if an egg breaks, you cannot drop it again. You know that there exists a floor F with 0 <= F <= N such that any egg dropped at a floor higher than F will break, and any egg dropped at or below floor F will not break. Each move, you may take an egg (if you have an unbroken one) and drop it from any floor X (with 1 <= X <= N). Your goal is to know with certainty what the value of F is. What is the minimum number of moves that you need to know with certainty what F is, regardless of the initial value of F? The idea is to use binary search to find the critical floor F. We can drop an egg from floor x and see if it breaks. If it does, then we know that the critical floor must be below x. If it doesn't break, then we know the critical floor must be above x.
This is a dynamic programming problem. We can define dp(K, N) to be the minimum number of drops needed to find the critical floor in N egg drops with K eggs.
The base case is dp(1, N) = N, since we need to try every floor from 1 to N with 1 egg.
For the general case, we can drop an egg from floor x.
If it breaks, then we only need to try floors 1 to x-1 with dp(K-1, x-1) drops.
If it doesn't break, then we only need to try floors x+1 to N with dp(K, N-x) drops.
We want to minimize the total number of drops, so we take the min of these two cases.
dp(K, N) = min(dp(K-1, x-1), dp(K, N-x)) + 1
We can further optimize this by using the fact that dp(K, N) = min(dp(K-1, x-1), dp(K, N-x)) + 1.
We can drop eggs from floors 1, 2, 3, ... until we either find the critical floor or we exceed the number of drops we are willing to make.
def superEggDrop(K, N):
dp = [0] * (K+1)
m = 0
# We need to try every floor from 1 to N
while dp[K] < N:
for x in range(1, K+1):
# If the egg breaks at floor x, we only need to try floors 1 to x-1
dp[x] = dp[x-1] + 1
# If the egg doesn't break at floor x, we only need to try floors x+1 to N
dp[K] = dp[K-1] + 1
m += 1
return mYou 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 if an egg breaks, you cannot drop it again.
You know that there exists a floor F with 0 <= F <= N such that any egg dropped at a floor higher than F will break, and any egg dropped at or below floor F will not break.
Each move, you may take an egg (if you have an unbroken one) and drop it from any floor X (with 1 <= X <= N).
Your goal is to know with certainty what the value of F is.
What is the minimum number of moves that you need to know with certainty what F is, regardless of the initial value of F?
// The idea is to use binary search to find the minimum number of drops needed to find the F floor,
// where the egg will not break when dropped from that floor.
// We can keep track of the minimum number of drops needed in a variable minDrops,
// and the maximum number of drops needed in a variable maxDrops.
// We can start our binary search with minDrops = 0 and maxDrops = N,
// and keep track of the midpoint of minDrops and maxDrops in a variable midDrops.
// If we drop an egg from floor midDrops and it breaks,
// then we know that the F floor must be somewhere between minDrops and midDrops-1.
// If the egg does not break, then we know that the F floor must be somewhere between midDrops+1 and maxDrops.
// We can keep track of the number of drops needed in a variable numDrops.
// If the egg breaks, we increment numDrops and set minDrops = midDrops+1.
// If the egg does not break, we set numDrops = numDrops+1 and maxDrops = midDrops.
// If numDrops > minDrops, then we know that we need to increment minDrops in order to find the F floor.
// We can keep track of the number of floors that we have already checked in a variable numFloors.
// If numFloors > minDrops, then we know that we have already found the F floor and we can return minDrops.
function superEggDrop(K, N) {
let minDrops = 0;
let maxDrops = N;
let midDrops;
let numDrops = 0;
let numFloors = 0;
while (minDrops <= maxDrops) {
midDrops = Math.floor((minDrops + maxDrops) / 2);
numDrops++;
numFloors++;
if (eggBreaks(midDrops)) {
minDrops = midDrops + 1;
} else {
maxDrops = midDrops;
}
if (numFloors > minDrops) {
return minDrops;
}
}
}
function eggBreaks(floor) {
// returns true if the egg breaks when dropped from the given floor, false otherwise
}There are K eggs and you have access to a building with N floors from 1 to N. Each egg is identical in function, and if an egg breaks, you cannot drop it again. You know that there exists a floor F with 0 <= F <= N such that any egg dropped at a floor higher than F will break, and any egg dropped at or below floor F will not break. Each move, you may take an egg (if you have an unbroken one) and drop it from any floor X (with 1 <= X <= N). Your goal is to know with certainty what the value of F is. What is the minimum number of moves that you need to know with certainty what F is, regardless of the initial value of F? The minimum number of moves needed to know the value of F is K. K eggs are needed to find the value of F with certainty. If fewer than K eggs are used, then the value of F cannot be determined with certainty.
using System;
public class Solution {
// We can use a dp array to store the minimum number of drops needed
// to get to a certain floor given a certain number of eggs
// For example, dp[2][10] would represent the minimum number of drops
// needed to get to floor 10 given 2 eggs
// We can populate the array using a bottom-up approach
// We know that if we only have 1 egg, we will need to make dp[1][k]
// drops to figure out the minimum floor the egg can break from
// We also know that if we have 0 floors, we will need 0 drops
// no matter how many eggs we have
// Therefore, we can set the base cases as follows:
// dp[1][k] = k
// dp[0][k] = 0
// We can then work our way up from there, using the following
// recursive formula:
// dp[i][j] = 1 + min(max(dp[i-1][k-1], dp[i][j-k]), for k in 1..j)
// Where the min is taken over all possible values of k
// The idea behind this is as follows:
// We need to make a decision at each level
// We can either drop the egg from floor k-1 and see if it breaks,
// in which case we already know the answer for dp[i-1][k-1]
// Or we can drop the egg from floor k and see if it breaks,
// in which case we already know the answer for dp[i][j-k]
// We then take the minimum of these two values, as we want to
// minimize the number of drops
// We also need to take into account the case where the egg breaks
// on the first try
// Therefore, the final formula is as follows:
// dp[i][j] = 1 + min(max(dp[i-1][k-1], dp[i][j-k]), for k in 1..j)
// if egg breaks on first try
// dp[i][j] = min(dp[i][j], 1 + dp[i-1][j])
public int SuperEggDrop(int K, int N) {
// Create a 2D array to store our dp values
int[][] dp = new int[K+1][N+1];
// Fill in the base cases
for (int i = 1; i <= K; i++) {
dp[i][0] = 0;
dp[i][1] = 1;
}
for (int j = 1; j <= N; j++) {
dp[1][j] = j;
}
// Work our way up from there
for (int i = 2; i <= K; i++) {
for (int j = 2; j <= N; j++) {
// Set the initial value to be a large number
dp[i][j] = Int32.MaxValue;
// Take into account all possible values of k
for (int k = 1; k <= j; k++) {
// Use our recursive formula to find the minimum number
// of drops needed
int val = 1 + Math.Max(dp[i-1][k-1], dp[i][j-k]);
if (val < dp[i][j]) {
dp[i][j] = val;
}
}
// Take into account the case where the egg breaks on
// the first try
if (dp[i-1][j] < dp[i][j]) {
dp[i][j] = 1 + dp[i-1][j];
}
}
}
// Return the minimum number of drops needed
return dp[K][N];
}
}