# Egg Drop With 2 Eggs and N Floors
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/egg-drop-with-2-eggs-and-n-floors)
Canonical: https://scaleengineer.com/dsa/problems/egg-drop-with-2-eggs-and-n-floors
**Patterns:** [Math](https://scaleengineer.com/dsa/patterns/math), [Dynamic Programming](https://scaleengineer.com/dsa/patterns/dynamic-programming)
**Companies:** [Citadel](https://scaleengineer.com/companies/citadel), [Disney](https://scaleengineer.com/companies/disney)
---
## 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.

**Example 1:**

**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:**

**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`

# Approaches
## Dynamic Programming
This approach uses dynamic programming to solve the problem. We build a DP array `dp` where `dp[i]` represents the minimum number of moves required to determine the critical floor `f` with certainty for a building with `i` floors and two eggs. We compute `dp[i]` for `i` from 1 to `n` by considering all possible floors for the first drop.
**Time:** O(n^2) due to the nested loops. The outer loop runs `n` times, and the inner loop runs up to `n` times. · **Space:** O(n) to store the DP array.
**Pros:** It's a standard and understandable dynamic programming solution.; Guaranteed to find the correct answer.
**Cons:** The time complexity is quadratic, which is inefficient for large values of `n`.; It uses linear space, which is more than other optimal approaches.
### Explanation
We define `dp[i]` as the minimum number of moves for `i` floors. To find `dp[i]`, we consider dropping the first egg from a floor `x` (where `1 <= x <= i`).

There are two outcomes:
1.  **Egg breaks:** We have one egg left and `x-1` floors below to check. With one egg, we must check each floor one by one from the bottom. This will take `x-1` more moves. The total moves in this case is `1 (for the current drop) + (x-1) = x`.
2.  **Egg does not break:** We still have two eggs, and we need to solve the problem for the `i-x` floors above floor `x`. This is a subproblem that requires `dp[i-x]` moves. The total moves in this case is `1 (for the current drop) + dp[i-x]`.

Since we need to find `f` with certainty, we must prepare for the worst-case scenario. For a given `x`, the number of moves is `max(x, 1 + dp[i-x])`. We want to choose the floor `x` that minimizes this worst-case number of moves.

The recurrence relation is: `dp[i] = min_{1 <= x <= i} (max(x, 1 + dp[i-x]))`.

We can compute `dp[i]` for `i = 1, 2, ..., n` by iterating through all possible values of `x` for each `i`. The base case is `dp[0] = 0`. The final answer is `dp[n]`.

```java
class Solution {
    public int twoEggDrop(int n) {
        // dp[i] stores the minimum moves for i floors.
        int[] dp = new int[n + 1];
        
        // Iterate through the number of floors from 1 to n.
        for (int i = 1; i <= n; i++) {
            dp[i] = Integer.MAX_VALUE;
            // Try dropping the first egg from every floor x from 1 to i.
            for (int x = 1; x <= i; x++) {
                // Case 1: Egg breaks at floor x.
                // We have 1 egg left and x-1 floors below to check.
                // This requires x-1 more linear checks. Total moves = 1 + (x-1) = x.
                int movesIfBreaks = x;
                
                // Case 2: Egg doesn't break at floor x.
                // We have 2 eggs left and i-x floors above to check.
                // This is the subproblem for i-x floors, which takes dp[i-x] moves.
                // Total moves = 1 + dp[i-x].
                int movesIfNotBreaks = 1 + dp[i - x];
                
                // The number of moves for a given x is the maximum of the two cases (worst-case).
                int worstCaseForX = Math.max(movesIfBreaks, movesIfNotBreaks);
                
                // We choose the floor x that minimizes this worst-case.
                dp[i] = Math.min(dp[i], worstCaseForX);
            }
        }
        return dp[n];
    }
}
```
### Algorithm
- Create a DP array `dp` of size `n + 1`, where `dp[i]` will store the minimum moves for `i` floors.
- The base case is `dp[0] = 0`.
- Loop for `i` from 1 to `n` to compute `dp[i]` for each number of floors.
- Inside this loop, initialize `dp[i]` to a large value.
- Start another nested loop for `x` from 1 to `i`. `x` represents the floor from which we drop the first egg.
- For each `x`, calculate the number of moves required in the worst-case scenario:
  - If the egg breaks: `x` moves are needed in total (1 for this drop + `x-1` for linear scan with the second egg).
  - If the egg doesn't break: `1 + dp[i-x]` moves are needed (1 for this drop + `dp[i-x]` for the remaining problem with `i-x` floors).
  - The worst case for a given `x` is `max(x, 1 + dp[i-x])`.
- Update `dp[i]` with the minimum worst-case found so far: `dp[i] = min(dp[i], max(x, 1 + dp[i-x]))`.
- After the loops complete, `dp[n]` holds the final answer.

## Iterative Approach
This approach reframes the problem. Instead of finding the minimum moves for `n` floors, we find the maximum number of floors we can cover with a given number of moves, `m`. We then iteratively increase `m` until we can cover at least `n` floors.
**Time:** O(sqrt(n)). The loop runs `k` times, where `k` is the result. We know `k * (k+1) / 2 >= n`, which means `k` is approximately `sqrt(2n)`. · **Space:** O(1) as we only use a few variables to store the state.
**Pros:** Much more efficient than the DP approach.; Very simple and intuitive logic.; Constant space complexity.
**Cons:** Slightly less efficient than the direct mathematical formula, though the difference is negligible for the given constraints.
### Explanation
Let's analyze the maximum number of floors, `F`, we can check with `k` moves. For our first drop (move 1), we drop an egg from floor `x`. 
- If it breaks, we have `k-1` moves and 1 egg left. With 1 egg, we can check `k-1` floors sequentially. So, `x-1` must be at most `k-1`, meaning `x <= k`.
- If it doesn't break, we have `k-1` moves and 2 eggs left. We can check `F(k-1)` more floors above `x`.
To maximize the total floors, we should choose `x=k`. This way, the total floors covered is `F(k) = (floors below) + (current floor) + (floors above) = (k-1) + 1 + F(k-1) = k + F(k-1)`.

This gives a recurrence `F(k) = k + F(k-1)`. With the base case `F(1) = 1`, we can see that `F(k) = k + (k-1) + ... + 1 = k * (k+1) / 2`.

So, the problem is to find the smallest integer `k` such that `k * (k+1) / 2 >= n`.
We can find this `k` by starting with `k=1` and incrementing it, while keeping track of the total floors covered (`k*(k+1)/2`).

```java
class Solution {
    public int twoEggDrop(int n) {
        int moves = 0;
        int floorsCovered = 0;
        while (floorsCovered < n) {
            moves++;
            floorsCovered += moves;
        }
        return moves;
    }
}
```
### Algorithm
- Initialize `moves = 0` and `floorsCovered = 0`.
- Start a loop that continues as long as `floorsCovered < n`.
- Inside the loop, increment `moves` by 1.
- Add the new `moves` to `floorsCovered`. This represents the new range of floors that can be checked with the second egg if the first one breaks at the current step.
- Once `floorsCovered` is greater than or equal to `n`, the loop terminates.
- Return `moves`.

## Mathematical Formula
This approach builds on the insight that with `k` moves, we can cover a maximum of `k * (k+1) / 2` floors. We can use this to form a quadratic inequality and solve for `k` directly using the quadratic formula, leading to a constant time solution.
**Time:** O(1) as the calculation involves a few arithmetic operations and a square root, which are considered constant time operations. · **Space:** O(1) as no extra space is used that depends on the input size `n`.
**Pros:** Most efficient solution with constant time and space complexity.; Provides a direct answer without iteration or recursion.
**Cons:** Requires mathematical insight to derive the formula, making it less intuitive than other approaches.
### Explanation
As established in the iterative approach, the problem is equivalent to finding the smallest integer `k` that satisfies the inequality: `k * (k+1) / 2 >= n`.

This can be rewritten as a quadratic inequality: `k^2 + k >= 2n`, or `k^2 + k - 2n >= 0`.

To find the boundary for `k`, we can solve the corresponding quadratic equation: `k^2 + k - 2n = 0`.
Using the quadratic formula, `k = (-b ± sqrt(b^2 - 4ac)) / 2a`, with `a=1`, `b=1`, `c=-2n`:
`k = (-1 ± sqrt(1^2 - 4 * 1 * (-2n))) / 2`
`k = (-1 ± sqrt(1 + 8n)) / 2`

Since the number of moves `k` must be positive, we take the positive root:
`k = (-1 + sqrt(1 + 8n)) / 2`

The solution `k` must be an integer. Since we are looking for the smallest integer `k` that satisfies the inequality, we need to take the ceiling of the result from the formula. This gives us a direct formula to calculate the result.

```java
class Solution {
    public int twoEggDrop(int n) {
        // We need to find the smallest k such that k * (k + 1) / 2 >= n.
        // This is equivalent to k^2 + k - 2n >= 0.
        // Solving for k in k^2 + k - 2n = 0 using the quadratic formula:
        // k = (-1 + sqrt(1 + 8n)) / 2
        // Since k must be an integer, we take the ceiling of this value.
        
        double k = (Math.sqrt(1 + 8.0 * n) - 1) / 2.0;
        return (int) Math.ceil(k);
    }
}
```
### Algorithm
- The problem is to find the smallest integer `k` such that `k * (k+1) / 2 >= n`.
- Rewrite this as a quadratic inequality: `k^2 + k - 2n >= 0`.
- Solve the corresponding equation `k^2 + k - 2n = 0` for `k` using the quadratic formula.
- The positive root is `k = (-1 + sqrt(1 + 8n)) / 2`.
- Since `k` must be an integer, take the ceiling of this result.
- Return the final integer value.

# Solutions
### Java

```java
class Solution {
public
  int twoEggDrop(int n) {
    int[][] dp = new int[n + 1][2];
    for (int i = 0; i <= n; i++)
      dp[i][0] = i;
    dp[1][1] = 1;
    for (int i = 2; i <= n; i++) {
      dp[i][1] = Integer.MAX_VALUE;
      for (int j = 1; j < i; j++) {
        int curr = Math.max(dp[j - 1][0], dp[i - j][1]) + 1;
        dp[i][1] = Math.min(dp[i][1], curr);
      }
    }
    return dp[n][1];
  }
}

```

### CPP

```cpp
// OJ: https://leetcode.com/problems/egg-drop-with-2-eggs-and-n-floors/ // Time: O(N^2) // Space: O(N) class Solution { public: int twoEggDrop ( int n ) { vector < int > dp ( n + 1 , INT_MAX ); dp [ 0 ] = 0 ; for ( int i = 1 ; i <= n ; ++ i ) { for ( int j = 1 ; j <= i ; ++ j ) { dp [ i ] = min ( dp [ i ], 1 + max ( j - 1 , dp [ i - j ])); } } return dp [ n ]; } };
```

### Python

```python
class Solution:
    def twoEggDrop(self, n: int) -> int: f = [0] + [inf] * n for i in range(1, n + 1): for j in range(1, i + 1): f[i] = min(f[i], 1 + max(j - 1, f[i - j])) return f[n]

```