Egg Drop With 2 Eggs and N Floors - Practice Coding Problems

Egg Drop With 2 Eggs and N Floors - Problem

You are given two 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.

In 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 — Small Building

$ Input: n = 2

› Output: 2

💡 Note: Drop first egg from floor 1. If it breaks, critical floor is 0 (2 moves). If it doesn't break, drop from floor 2. If it breaks, critical floor is 1, otherwise critical floor is 2 (2 moves total).

Example 2 — Medium Building

$ Input: n = 10

› Output: 4

💡 Note: Using optimal strategy: drop from floors 4, 7, 9, 10. This guarantees finding the critical floor in at most 4 moves regardless of where it is.

Example 3 — Single Floor

$ Input: n = 1

› Output: 1

💡 Note: Only one floor to test. Drop the egg from floor 1. If it breaks, critical floor is 0, otherwise it's 1. Only 1 move needed.

Constraints

1 ≤ n ≤ 1000

Visualization

Tap to expand

Understanding the Visualization

Input

Building with n floors, 2 identical eggs

Process

Strategic dropping to minimize worst-case moves

Output

Minimum moves to guarantee finding critical floor f

Key Takeaway

🎯 Key Insight: Balance worst-case outcomes by using triangular number formula

Asked in

G Google 35 M Microsoft 28 A Amazon 22 f Facebook 18

The key insight is to balance worst-case scenarios for both egg outcomes. The optimal strategy uses triangular numbers to minimize maximum drops. Best approach is the mathematical formula m = ceil((-1 + sqrt(1 + 8n)) / 2). Time: O(√n), Space: O(1)

Common Approaches

Approach	Time	Space	Notes
✓ Linear Search Strategy	O(n)	O(1)	Drop first egg from floor 1, 2, 3... until it breaks, then use second egg
Optimal Mathematical Strategy	O(√n)	O(1)	Use triangular numbers to balance worst-case scenarios optimally
Dynamic Programming Approach	O(n²)	O(n)	Build up solution using DP to find minimum drops for each floor count

Linear Search Strategy — Algorithm Steps

Drop first egg from floors 1, 2, 3... until it breaks at floor k
Use second egg to test floors from 1 to k-1 linearly
Total moves = (k-1) + (k-1) = 2k-2 in worst case

Visualization

Tap to expand

Step-by-Step Walkthrough

Sequential Drops

Drop first egg from floors 1,2,3... until break

Linear Search

Use second egg to search linearly below break point

Result

Total moves can be up to 2n-1

Code -

solution.c — C

#include <stdio.h>

int solution(int n) {
    // Worst case: first egg breaks at floor n
    // Need n-1 drops for first egg + n-1 drops for second egg
    return n;
}

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

Time & Space Complexity

Time Complexity

⏱️

O(n)

Single pass through floors, worst case n drops

✓ Linear Growth

Space Complexity

O(1)

Only uses constant extra variables

✓ Linear Space

32.0K Views

Medium Frequency

~25 min Avg. Time

890 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

Linear Search Strategy — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler