Super Egg Drop - Practice Coding Problems

Super Egg Drop - Problem

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
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.

Input & Output

Example 1 — Basic Case

$ Input: k = 1, n = 2

› Output: 2

💡 Note: With only 1 egg, we must try floors sequentially: drop from floor 1, then floor 2 if it doesn't break. Worst case is 2 moves.

Example 2 — Multiple Eggs

$ Input: k = 2, n = 6

› Output: 3

💡 Note: With 2 eggs and 6 floors, optimal strategy: drop from floor 3. If breaks, try floors 1,2 with remaining egg (3 total moves). If survives, drop from floor 5, then check remaining floors.

Example 3 — Many Eggs

$ Input: k = 3, n = 14

› Output: 4

💡 Note: With 3 eggs, we can use more aggressive binary search strategy, requiring only 4 moves in worst case for 14 floors.

Constraints

1 ≤ k ≤ 100
1 ≤ n ≤ 10⁴

Visualization

Tap to expand

Understanding the Visualization

Input

k=2 eggs, n=6 floors building

Strategy

Find optimal floors to test

Output

Minimum 3 moves needed

Key Takeaway

🎯 Key Insight: Think backwards - with t moves and k eggs, what's the maximum floors we can handle? Binary search on the answer is most efficient.

Asked in

G Google 15 M Microsoft 12 a Amazon 8

The key insight is to think backwards: instead of asking "what's the minimum moves for k eggs and n floors?", ask "with t moves and k eggs, what's the maximum floors we can handle?". The best approach uses binary search on the answer with mathematical optimization. Time: O(k log n), Space: O(1)

Common Approaches

Approach	Time	Space	Notes
✓ Binary Search on Answer	O(k log n)	O(1)	Binary search on the number of moves, check if it's sufficient
Recursive Dynamic Programming	O(kn²)	O(kn)	Try all possible floors and recursively solve subproblems
Optimized 2D DP	O(kn log n)	O(kn)	Bottom-up DP with binary search optimization for floor selection

Binary Search on Answer — Algorithm Steps

Binary search on moves from 1 to n
For each move count, calculate max floors we can handle
Use formula: with t moves and k eggs, max floors = sum of binomial coefficients

Visualization

Tap to expand

Step-by-Step Walkthrough

Search Space

Moves from 1 to n

Check Mid

Can handle n floors in mid moves?

Narrow Down

Adjust search space based on result

Code -

solution.c — C

#include <stdio.h>
#include <stdbool.h>

bool canHandle(int moves, int eggs, int floors) {
    if (moves == 0) return floors == 0;
    if (eggs == 1) return floors <= moves;
    
    long long maxFloors = 0;
    long long coeff = 1;
    int maxEggs = eggs < moves ? eggs : moves;
    
    for (int i = 1; i <= maxEggs; i++) {
        coeff = coeff * (moves - i + 1) / i;
        maxFloors += coeff;
        if (maxFloors >= floors) return true;
    }
    return maxFloors >= floors;
}

int solution(int k, int n) {
    int left = 1, right = n;
    while (left < right) {
        int mid = (left + right) / 2;
        if (canHandle(mid, k, n)) {
            right = mid;
        } else {
            left = mid + 1;
        }
    }
    return left;
}

int main() {
    int k, n;
    scanf("%d", &k);
    scanf("%d", &n);
    printf("%d\n", solution(k, n));
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(k log n)

Binary search O(log n) with O(k) calculation per iteration

⚡ Linearithmic

Space Complexity

O(1)

Only variables for binary search and calculation

✓ Linear Space

89.0K Views

Medium Frequency

~35 min Avg. Time

2.1K Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Binary Search on Answer — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler