Super Egg Drop Puzzle — Dynamic Programming
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 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
?
Example 1:
Input: K = 1, N = 2
Output: 2
Explanation:
Drop the egg from floor 1. If it breaks, we know with certainty that F = 0.
Otherwise, drop the egg from floor 2. If it breaks, we know with certainty that F = 1.
If it didn't break, then we know with certainty F = 2.
Hence, we needed 2 moves in the worst case to know what F is with certainty.
Example 2:
Input: K = 2, N = 6
Output: 3
Example 3:
Input: K = 3, N = 14
Output: 4
Note:
1 <= K <= 100
1 <= N <= 10000
Solution :
class Solution {
Integer dp[][]=new Integer[101][10001];
//Declared wrapper class because no need to initialise values, will be null defaultly
public int superEggDrop(int K, int N) {
if(K==1)//when there is only one egg
return N;
if(N==0 || N==1)//when no. of floors are 0 or 1
return N;
if(dp[K][N]!=null)//checking if it is filled
return dp[K][N];
int i,l=1,h=N;
int ans=Integer.MAX_VALUE;
while(l<=h)
{
int mid=(l+h)/2;
int down_temp=superEggDrop(K-1,mid-1);//If egg breaks go down
int up_temp=superEggDrop(K,N-mid);//if egg doesn't break go up
int temp=1+Math.max(down_temp,up_temp);
//adding one because we have used 1 attempt and max of up and down because
//we need worst case attempts from both
if(down_temp<up_temp)//if down attempts are less we only require upper ones and vise versa
l=mid+1;
else
h=mid-1;
ans=Math.min(temp,ans);//this is beacuse we need minimum of all worst case attempts
}
return dp[K][N]=ans;
}
}