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?
Constraints
1 <= K <= 100
1 <= N <= 10000
Approach
Links
GeeksforGeeks
ProgramCreek
YouTube
Examples
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.
Input: K = 2, N = 6
Output: 3
Input: K = 3, N = 14
Output: 4
Solutions
/**
* Time complexity : O(K*NlogN)
* Space complexity : O(K*N)
*/
class Solution {
public int superEggDrop(int K, int N) {
int[][] memo = new int[K+1][N+1];
return helper(K, N, memo);
}
private int helper(int eggs, int floors, int[][] memo) {
if(eggs == 1 || floors <= 1) {
return floors;
}
if(memo[eggs][floors] > 0) {
return memo[eggs][floors];
}
int min = Integer.MAX_VALUE;
int low = 1, high = floors;
while(low < high) {
int mid = (low + high)/2;
int breakMove = helper(eggs-1, mid-1, memo);
int safeMove = helper(eggs, floors-mid, memo);
min = Math.min(min, 1+Math.max(breakMove, safeMove));
if(breakMove == safeMove) {
break;
} else if(breakMove > safeMove) {
high = mid;
} else {
low = mid + 1;
}
}
memo[eggs][floors] = min;
return min;
}
}
/**
* Time complexity : O(K*N)
* Space complexity : O(N)
*/
class Solution {
public int superEggDrop(int K, int N) {
int[] dp = new int[N+1];
for(int i = 0; i <= N; i++) {
dp[i] = i;
}
for(int k = 2; k <= K; k++) {
int[] dp2 = new int[N+1];
int x = 1;
for(int n = 1; n <= N; n++) {
while(x < n && Math.max(dp[x-1], dp2[n-x]) > Math.max(dp[x], dp2[n-x-1])) {
x++;
}
dp2[n] = 1 + Math.max(dp[x-1], dp2[n-x]);
}
dp = dp2;
}
return dp[N];
}
}
/**
* Time complexity : O(K*N)
* Space complexity : O(K*N)
*/
class Solution {
public int superEggDrop(int K, int N) {
int[][] dp = new int[K+1][N+1];
int m = 0;
while(dp[K][m] < N) {
m++;
for(int k = 1; k <= K; k++) {
dp[k][m] = dp[k][m-1] + dp[k-1][m-1] + 1;
}
}
return m;
}
}