You are given k identical eggs and you have access to a building with n floors labeled from 1 to n.
You know that there exists a floor f where 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 unbroken egg and drop it from any floor x (where 1 <= x <= n). If the egg breaks, you can no longer use it. However, if the egg does not break, you may reuse it in future moves.
Return the minimum number of moves that you need to determine with certainty what the value off is.
Input: k =1, n =2Output: 2Explanation:
Drop the egg from floor 1. If it breaks, we know that f =0.Otherwise, drop the egg from floor 2. If it breaks, we know that f =1.If it does not break, then we know f =2.Hence, we need at minimum 2 moves to determine with certainty what the value of f is.
Brute-force every possible first drop floor x (1..h). For each x we consider two outcomes: egg breaks (search below with one fewer egg) or egg survives (search above with same eggs). We take the worse (max) because we require certainty, then choose the x that minimizes this worst-case.
classSolutionNaive {
public:int superEggDrop(int k, int n) { returnsolve(k, n); }
private:int solve(int e, int h) {
if (h ==0|| h ==1) return h;
if (e ==1) return h;
int best = INT_MAX;
for (int x =1; x <= h; ++x) {
int broken = solve(e -1, x -1);
int survive = solve(e, h - x);
int worst =1+ std::max(broken, survive);
if (worst < best) best = worst;
}
return best;
}
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
classSolutionNaive {
publicintsuperEggDrop(int k, int n) { return solve(k, n); }
privateintsolve(int e, int h) {
if (h == 0 || h == 1) return h;
if (e == 1) return h;
int best = Integer.MAX_VALUE;
for (int x = 1; x <= h; x++) {
int broken = solve(e - 1, x - 1);
int survive = solve(e, h - x);
int worst = 1 + Math.max(broken, survive);
if (worst < best) best = worst;
}
return best;
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
classSolutionNaive:
defsuperEggDrop(self, k: int, n: int) -> int:
defsolve(e: int, h: int) -> int:
if h <=1:
return h
if e ==1:
return h
best = float('inf')
for x in range(1, h +1):
worst =1+ max(solve(e -1, x -1), solve(e, h - x))
if worst < best:
best = worst
return best
return solve(k, n)
classSolutionMemo {
std::vector<std::vector<int>> memo; // -1 = uncomputed
public:int superEggDrop(int k, int n) {
memo.assign(k+1, std::vector<int>(n+1, -1));
returnsolve(k, n);
}
private:int solve(int e, int h) {
if (h <=1) return h;
if (e ==1) return h;
int&ref = memo[e][h];
if (ref !=-1) return ref;
int best = INT_MAX;
for (int x =1; x <= h; ++x) {
int broken = solve(e -1, x -1);
int survive = solve(e, h - x);
int worst =1+ std::max(broken, survive);
if (worst < best) best = worst;
}
return ref = best;
}
};
import java.util.Arrays;
classSolutionMemo {
privateint[][] memo;
publicintsuperEggDrop(int k, int n) {
memo =newint[k+1][n+1];
for (int[] row : memo) Arrays.fill(row, -1);
return solve(k, n);
}
privateintsolve(int e, int h) {
if (h <= 1) return h;
if (e == 1) return h;
if (memo[e][h]!=-1) return memo[e][h];
int best = Integer.MAX_VALUE;
for (int x = 1; x <= h; x++) {
int broken = solve(e - 1, x - 1);
int survive = solve(e, h - x);
int worst = 1 + Math.max(broken, survive);
if (worst < best) best = worst;
}
return memo[e][h]= best;
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
from functools import lru_cache
classSolutionMemo:
defsuperEggDrop(self, k: int, n: int) -> int:
@lru_cache(None)
defsolve(e: int, h: int) -> int:
if h <=1:
return h
if e ==1:
return h
best = float('inf')
for x in range(1, h +1):
worst =1+ max(solve(e -1, x -1), solve(e, h - x))
if worst < best:
best = worst
return best
return solve(k, n)
Fill dp[e][h] using recurrence. For fixed (e,h), broken(x)=dp[e-1][x-1] increases with x; survive(x)=dp[e][h-x] decreases with x. The maximum of a non-decreasing and a non-increasing sequence is unimodal → binary search finds optimal x.
classSolution {
public:int superEggDrop(int K, int N) {
std::vector<std::vector<int>> dp(K+1, std::vector<int>(N+1, 0));
for (int h =0; h <= N; ++h) dp[1][h] = h;
for (int e =2; e <= K; ++e) {
dp[e][1] =1;
for (int h =2; h <= N; ++h) {
int lo =1, hi = h;
while (lo < hi) {
int mid = (lo + hi) /2;
int broken = dp[e-1][mid-1];
int survive = dp[e][h-mid];
if (broken < survive) lo = mid +1; else hi = mid;
}
dp[e][h] =1+ dp[e-1][lo-1];
}
}
return dp[K][N];
}
};
classSolution {
publicintsuperEggDrop(int k, int n) {
int[][] dp =newint[k + 1][n + 1];
for (int h = 0; h <= n; h++) dp[1][h]= h;
for (int e = 2; e <= k; e++) {
dp[e][1]= 1;
for (int h = 2; h <= n; h++) {
int lo = 1, hi = h;
while (lo < hi) {
int mid = (lo + hi) / 2;
int broken = dp[e - 1][mid - 1];
int survive = dp[e][h - mid];
if (broken < survive) lo = mid + 1; else hi = mid;
}
dp[e][h]= 1 + dp[e - 1][lo - 1];
}
}
return dp[k][n];
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
classSolution:
defsuperEggDrop(self, k: int, n: int) -> int:
dp = [[0]*(n+1) for _ in range(k+1)]
for h in range(n+1):
dp[1][h] = h
for e in range(2, k+1):
dp[e][1] =1for h in range(2, n+1):
lo, hi =1, h
while lo < hi:
mid = (lo + hi)//2 broken = dp[e-1][mid-1]
survive = dp[e][h-mid]
if broken < survive:
lo = mid +1else:
hi = mid
dp[e][h] =1+ dp[e-1][lo-1]
return dp[k][n]
classSolutionKt {
funsuperEggDrop(k: Int, n: Int): Int {
val dp = Array(k+1) { IntArray(n+1) }
for (h in0..n) dp[1][h] = h
for (e in2..k) {
dp[e][1] = 1for (h in2..n) {
var lo = 1; var hi = h
while (lo < hi) {
val mid = (lo + hi) / 2val broken = dp[e-1][mid-1]
val survive = dp[e][h-mid]
if (broken < survive) lo = mid + 1else hi = mid
}
dp[e][h] = 1 + dp[e-1][lo-1]
}
}
return dp[k][n]
}
}
impl Solution {
pubfnsuper_egg_drop(k: i32, n: i32) -> i32 {
let k = k asusize; let n = n asusize;
letmut dp =vec![vec![0; n+1]; k+1];
for h in0..=n { dp[1][h] = h asi32; }
for e in2..=k {
dp[e][1] =1;
for h in2..=n {
let (mut lo, mut hi) = (1usize, h);
while lo < hi {
let mid = (lo + hi)/2;
let broken = dp[e-1][mid-1];
let survive = dp[e][h-mid];
if broken < survive { lo = mid +1; } else { hi = mid; }
}
dp[e][h] =1+ dp[e-1][lo-1];
}
}
dp[k][n]
}
}