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 _theminimum number of moves that you need to determine with certainty what the value of _f is.

Examples

Example 1

1
2
3
4
5
6

Input: n = 2
Output: 2
Explanation: We can drop the first egg from floor 1 and the second egg from floor 2.
If the first egg breaks, we know that f = 0.
If the second egg breaks but the first egg didn't, we know that f = 1.
Otherwise, if both eggs survive, we know that f = 2.

Example 2

1
2
3
4
5
6
7

Input: n = 100
Output: 14
Explanation: One optimal strategy is:
- Drop the 1st egg at floor 9. If it breaks, we know f is between 0 and 8. Drop the 2nd egg starting from floor 1 and going up one at a time to find f within 8 more drops. Total drops is 1 + 8 = 9.
- If the 1st egg does not break, drop the 1st egg again at floor 22. If it breaks, we know f is between 9 and 21. Drop the 2nd egg starting from floor 10 and going up one at a time to find f within 12 more drops. Total drops is 2 + 12 = 14.
- If the 1st egg does not break again, follow a similar process dropping the 1st egg from floors 34, 45, 55, 64, 72, 79, 85, 90, 94, 97, 99, and 100.
Regardless of the outcome, it takes at most 14 drops to determine f.

Constraints

  • 1 <= n <= 1000
Similar Problems

Solution

Method 1 - Naive Linear Scan

Intuition

Your first instinct might be: “Can I binary search the floors?” With only 2 eggs, pure binary search fails because once the first egg breaks (say at mid), you have just one egg left and must linearly probe all lower candidate floors. So instead of pretending we can divide the space evenly, the most basic guaranteed strategy is simply to walk floors one by one until the egg breaks (or we reach the top). Worst case: the break threshold f is the top floor → n drops.

Approach

  1. Start from floor 1 and increment upward.
  2. Drop an egg each floor until it breaks or you reach n.
  3. The number of drops in worst case is n.

This is our correctness baseline to improve upon.

Code

1
2
3
4
5
6
7

class SolutionLinear {
public:
    int twoEggDrop(int n) {
        // Worst case we test every floor
        return n; // explicit linear scan implied
    }
};
1
2
3
4
5

class SolutionLinear {
    public int twoEggDrop(int n) {
        return n; // linear worst case
    }
}
1
2
3

class SolutionLinear:
    def twoEggDrop(self, n: int) -> int:
        return n  # linear worst case

Complexity

  • ⏰ Time complexity: O(n) – may inspect every floor.
  • 🧺 Space complexity: O(1) – constant.

Method 2 - Naive Recursion

Intuition

Try every possible first drop floor x (1..n). Two outcomes:

  • Egg breaks → must linearly search the x-1 lower floors with 1 egg (cost x-1 additional drops in worst case).
  • Egg survives → still have 2 eggs, but only n - x higher floors remain.

So worst-case moves if we pick x first: 1 + max( x-1, solve(n - x) ). We brute-force all x and take minimum.

Approach

  • Define solve(h) = min worst-case drops for h floors and 2 eggs.
  • Base: solve(0)=0, solve(1)=1.
  • Recurse enumerating x.

Recurrence

1

solve(h) = 1 + min_{1<=x<=h} max( x-1, solve(h - x) )

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

class SolutionRecNaive {
public:
    int twoEggDrop(int n) { return dfs(n); }
private:
    int dfs(int h) {
        if (h <= 1) return h;
        int best = INT_MAX;
        for (int x = 1; x <= h; ++x) {
            int worst = 1 + std::max(x - 1, dfs(h - x));
            if (worst < best) best = worst;
        }
        return best;
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

class SolutionRecNaive {
    public int twoEggDrop(int n) { return dfs(n); }
    private int dfs(int h) {
        if (h <= 1) return h;
        int best = Integer.MAX_VALUE;
        for (int x = 1; x <= h; x++) {
            int worst = 1 + Math.max(x - 1, dfs(h - x));
            if (worst < best) best = worst;
        }
        return best;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

class SolutionRecNaive:
    def twoEggDrop(self, n: int) -> int:
        def dfs(h: int) -> int:
            if h <= 1:
                return h
            best = float('inf')
            for x in range(1, h + 1):
                worst = 1 + max(x - 1, dfs(h - x))
                if worst < best:
                    best = worst
            return best
        return dfs(n)

Complexity

  • ⏰ Time complexity: O(2^n) – exponential due to severe recomputation over splits.
  • 🧺 Space complexity: O(n) – recursion depth.

Method 3 - Memoized Recursion (Top-Down DP)

Intuition

Same recurrence as Method 2 but cache by h. Only n distinct states; for each we scan all x.

Approach

  • Memo array / map of length n+1.
  • Return cached value if already computed.

Recurrence

solve(h) = 1 + min_{x} max(x-1, solve(h - x)).

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20

class SolutionRecMemo {
    std::vector<int> memo;
public:
    int twoEggDrop(int n) {
        memo.assign(n+1, -1);
        return solve(n);
    }
private:
    int solve(int h) {
        if (h <= 1) return h;
        int &ref = memo[h];
        if (ref != -1) return ref;
        int best = INT_MAX;
        for (int x = 1; x <= h; ++x) {
            int worst = 1 + std::max(x - 1, solve(h - x));
            if (worst < best) best = worst;
        }
        return ref = best;
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19

import java.util.Arrays;
class SolutionRecMemo {
    private int[] memo;
    public int twoEggDrop(int n) {
        memo = new int[n+1];
        Arrays.fill(memo, -1);
        return solve(n);
    }
    private int solve(int h) {
        if (h <= 1) return h;
        if (memo[h] != -1) return memo[h];
        int best = Integer.MAX_VALUE;
        for (int x = 1; x <= h; x++) {
            int worst = 1 + Math.max(x - 1, solve(h - x));
            if (worst < best) best = worst;
        }
        return memo[h] = best;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

from functools import lru_cache

class SolutionRecMemo:
    def twoEggDrop(self, n: int) -> int:
        @lru_cache(None)
        def solve(h: int) -> int:
            if h <= 1:
                return h
            best = float('inf')
            for x in range(1, h + 1):
                worst = 1 + max(x - 1, solve(h - x))
                if worst < best:
                    best = worst
            return best
        return solve(n)

Complexity

  • ⏰ Time complexity: O(n^2) – n states × up to n first-drop trials.
  • 🧺 Space complexity: O(n) – memo + recursion stack.

Method 4 - Bottom-Up DP

Intuition

Iteratively compute dp[h] for h=0..n using the recurrence. This is a classic 1D DP equivalent to the memoized version but avoids recursion. For each h, scanning x balances the two outcomes: break (linear scan cost below) vs survive (reuse result of dp[h - x]).

Approach

  1. Initialize dp[0]=0, dp[1]=1.
  2. For h=2..n, compute dp[h] = 1 + min_{1<=x<=h} max(x-1, dp[h - x]).
  3. Return dp[n].

Recurrence

dp[h] = 1 + min_{x} max(x-1, dp[h - x]).

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

class SolutionDP {
public:
    int twoEggDrop(int n) {
        std::vector<int> dp(n+1, 0);
        if (n >= 1) dp[1] = 1;
        for (int h = 2; h <= n; ++h) {
            int best = INT_MAX;
            for (int x = 1; x <= h; ++x) {
                int worst = 1 + std::max(x - 1, dp[h - x]);
                if (worst < best) best = worst;
            }
            dp[h] = best;
        }
        return dp[n];
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

class SolutionDP {
    public int twoEggDrop(int n) {
        int[] dp = new int[n+1];
        if (n >= 1) dp[1] = 1;
        for (int h = 2; h <= n; h++) {
            int best = Integer.MAX_VALUE;
            for (int x = 1; x <= h; x++) {
                int worst = 1 + Math.max(x - 1, dp[h - x]);
                if (worst < best) best = worst;
            }
            dp[h] = best;
        }
        return dp[n];
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

class SolutionDP:
    def twoEggDrop(self, n: int) -> int:
        if n <= 1:
            return n
        dp = [0]*(n+1)
        dp[1] = 1
        for h in range(2, n+1):
            best = float('inf')
            for x in range(1, h+1):
                worst = 1 + max(x - 1, dp[h - x])
                if worst < best:
                    best = worst
            dp[h] = best
        return dp[n]

Complexity

  • ⏰ Time complexity: O(n^2) – nested loops over h and x.
  • 🧺 Space complexity: O(n) – 1D DP array.

Method 5 - Incremental Jump (Mathematical / Triangular Strategy)

Intuition

Because we have exactly two eggs, we can afford to “sacrifice” the first one through a sequence of planned jumps, but we must preserve the second for a final linear sweep when the first breaks. We want to minimize the worst-case number of drops (a minimax objective). Suppose the optimal worst-case number of moves is x. Then the FIRST jump cannot exceed x: if we naïvely jumped to floor x+1 and the egg shattered, we would still need up to x additional linear drops with the second egg (floors 1..x), totaling x+1 moves — contradicting optimality.

So the largest safe initial jump (under optimality) is exactly x. If that first drop survives, our second jump must now be at most x-1 floors higher (for the same reasoning: we must leave at most x-1 reserve linear moves if it breaks there). Continuing this logic, the jump sizes must be:

1

x, (x-1), (x-2), ..., 1

These decreasing increments guarantee that no matter at which jump the first egg breaks, the remaining floors below the breaking point can be exhaustively checked within the leftover moves budget. In the worst case (egg never breaks until coverage exhausted) we cover a total of the triangular number:

1

x + (x-1) + (x-2) + ... + 1 = x(x+1)/2

We therefore need the smallest integer x such that:

1

x(x + 1)/2 >= n

Equivalently solve the quadratic inequality x^2 + x - 2n >= 0 and take the positive root:

1

x = ( -1 + sqrt(1 + 8n) ) / 2

If this root is integral, that is the answer; otherwise we round up (ceil). Example: n = 105 gives x = ( -1 + sqrt(841) )/2 = ( -1 + 29 )/2 = 14. Jump sequence covers floors cumulatively: 14, 27, 39, 50, 60, 69, 77, 84, 90, 95, 99, 102, 104, 105. Each increment shrinks by 1.

Approach

  1. Compute the minimal x whose triangular number ≥ n either by loop accumulation or closed form.
  2. (Loop variant) Repeatedly add step=1,2,3,... until sum ≥ n — number of steps is x.
  3. This x is the worst-case minimum number of moves.

Example (n = 10)

Triangular progression: 1, 3, 6, 10 → smallest ≥ 10 is 10 with x=4. Planned drops: 4, 7, 9, 10. Worst-case 4 drops.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

class Solution {
public:
    int twoEggDrop(int n) {
        int k = 0, sum = 0;
        while (sum < n) {
            k++;
            sum += k;
        }
        return k;
    }
};
1
2
3
4
5
6
7
8

func twoEggDrop(n int) int {
    k, sum := 0, 0
    for sum < n {
        k++
        sum += k
    }
    return k
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10

class Solution {
    public int twoEggDrop(int n) {
        int k = 0, sum = 0;
        while (sum < n) {
            k++;
            sum += k;
        }
        return k;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

class Solution {
    fun twoEggDrop(n: Int): Int {
        var k = 0
        var sum = 0
        while (sum < n) {
            k++
            sum += k
        }
        return k
    }
}
1
2
3
4
5
6
7
8

class Solution:
    def twoEggDrop(self, n: int) -> int:
        k = 0
        sum_ = 0
        while sum_ < n:
            k += 1
            sum_ += k
        return k
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

impl Solution {
    pub fn two_egg_drop(n: i32) -> i32 {
        let mut k = 0;
        let mut sum = 0;
        while sum < n {
            k += 1;
            sum += k;
        }
        k
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10

class Solution {
    twoEggDrop(n: number): number {
        let k = 0, sum = 0;
        while (sum < n) {
            k++;
            sum += k;
        }
        return k;
    }
}

Complexity

  • ⏰ Time complexity: O(k) – where k = answer ≈ sqrt(2n); loop grows triangularly until coverage ≥ n.
  • 🧺 Space complexity: O(1) – constant counters.

Method 6 - Direct Formula (Closed Form)

Intuition

Solve k(k+1)/2 >= n for minimal integer k. Quadratic inequality: k^2 + k - 2n >= 0 ⇒ positive root k = ( -1 + sqrt(1 + 8n) ) / 2. Take ceiling.

Approach

  1. Compute k = ceil( (sqrt(8n + 1) - 1) / 2 ).
  2. Return k.

Code

1
2
3
4
5
6

class SolutionFormula {
public:
    int twoEggDrop(int n) {
        return (int)std::ceil((std::sqrt(8.0 * n + 1) - 1) / 2.0);
    }
};
1
2
3
4
5

class SolutionFormula {
    public int twoEggDrop(int n) {
        return (int)Math.ceil((Math.sqrt(8.0 * n + 1) - 1.0) / 2.0);
    }
}
1
2
3
4
5

import math

class SolutionFormula:
    def twoEggDrop(self, n: int) -> int:
        return math.ceil((math.sqrt(8 * n + 1) - 1) / 2)

Complexity

  • ⏰ Time complexity: O(1) – constant arithmetic.
  • 🧺 Space complexity: O(1).