Problem Statement:
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 of f is.
Examples:
Example 1:
Input: k = 1, n = 2
Output: 2
Explanation:
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.
Example 2:
Input: k = 2, n = 6
Output: 3
Example 3:
Input: k = 3, n = 14
Output: 4
Constraints
1 <= k <= 100
1 <= n <= 104
Time Complexity:
Time Complexity = O(k x moves)
Space Complexity:
Space Complexity = O(k)
Approach
-
Instead of directly finding the
minimum movesfor k eggs and n floors, we reverse the thinking. We calculate how many floors can be tested with a given number of moves and eggs. -
Let
dp[i]represent the maximum number of floors that can be checked usingieggs and the current number of moves. - Initialize a DP array of size k + 1 with all values 0.
- Increase the
number of movesstep by step until we can check atleast n floorswithk eggs. - For every move, update the DP values from right to left using the relation:
If an egg is dropped:- Egg breaks → we check floors below with
i-1 eggs. - Egg survives → we check floors above with
i eggs.
- Egg breaks → we check floors below with
- So the recurrence becomes:
dp[i] = 1 + dp[i] + dp[i-1]where:1= current floor,dp[i]= floors we can check if egg survives anddp[i-1]= floors we can check if egg breaks.
- Continue increasing moves until
dp[k] >= n. - The number of moves taken is the minimum number of attempts required in the worst case.
Dry Run
Input: k = 2, n = 6
Meaning:
dp[i] = maximum floors we can test with i eggs and current number of moves
Initialization:
dp = [0, 0, 0] (index 0..k)
moves = 0
Step 1: moves = 1
Update dp from right to left
i = 2
dp[2] = 1 + dp[2] + dp[1]
= 1 + 0 + 0
= 1
i = 1
dp[1] = 1 + dp[1] + dp[0]
= 1 + 0 + 0
= 1
dp = [0, 1, 1]
Interpretation:
With 1 move:
1 egg → test 1 floor
2 eggs → test 1 floor
Condition check:
dp[2] = 1 < 6 → continue
Step 2: moves = 2
i = 2
dp[2] = 1 + dp[2] + dp[1]
= 1 + 1 + 1
= 3
i = 1
dp[1] = 1 + dp[1] + dp[0]
= 1 + 1 + 0
= 2
dp = [0, 2, 3]
Interpretation:
With 2 moves:
1 egg → test 2 floors
2 eggs → test 3 floors
Condition check:
dp[2] = 3 < 6 → continue
Step 3: moves = 3
i = 2
dp[2] = 1 + dp[2] + dp[1]
= 1 + 3 + 2
= 6
i = 1
dp[1] = 1 + dp[1] + dp[0]
= 1 + 2 + 0
= 3
dp = [0, 3, 6]
Interpretation:
With 3 moves:
1 egg → test 3 floors
2 eggs → test 6 floors
Condition check:
dp[2] = 6 ≥ 6 → stop
Output: 3
var superEggDrop = function(k, n) {
let dp = new Array(k + 1).fill(0);
let moves = 0;
while(dp[k] < n){
moves++;
for(let i = k; i >= 1; i--) {
dp[i] = 1 + dp[i] + dp[i-1];
}
}
return moves;
};
def superEggDrop(k, n):
dp = [0] * (k + 1)
moves = 0
while dp[k] < n:
moves += 1
for i in range(k, 0, -1):
dp[i] = 1 + dp[i] + dp[i-1]
return moves
class Solution {
public int superEggDrop(int k, int n) {
int[] dp = new int[k + 1];
int moves = 0;
while(dp[k] < n){
moves++;
for(int i = k; i >= 1; i--){
dp[i] = 1 + dp[i] + dp[i-1];
}
}
return moves;
}
}
#include <vector>
using namespace std;
class Solution {
public:
int superEggDrop(int k, int n) {
vector dp(k + 1, 0);
int moves = 0;
while(dp[k] < n){
moves++;
for(int i = k; i >= 1; i--){
dp[i] = 1 + dp[i] + dp[i-1];
}
}
return moves;
}
};
#include <stdio.h>
int superEggDrop(int k, int n) {
int dp[k + 1];
for(int i = 0; i <= k; i++)
dp[i] = 0;
int moves = 0;
while(dp[k] < n){
moves++;
for(int i = k; i >= 1; i--){
dp[i] = 1 + dp[i] + dp[i-1];
}
}
return moves;
}
public class Solution {
public int SuperEggDrop(int k, int n) {
int[] dp = new int[k + 1];
int moves = 0;
while(dp[k] < n){
moves++;
for(int i = k; i >= 1; i--){
dp[i] = 1 + dp[i] + dp[i - 1];
}
}
return moves;
}
}
