> For the complete documentation index, see [llms.txt](https://mayanktyagi3111.gitbook.io/interview-prep/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://mayanktyagi3111.gitbook.io/interview-prep/dynamic-programming/egg-dropping-puzzle.md).

# Egg Dropping Puzzle

You are given `K` eggs, and you have access to a building with `N` floors from `1` to `N`. 

Each egg is identical in function, and if an egg breaks, you cannot drop it again.

You know that there exists a floor `F` with `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 egg (if you have an unbroken one) and drop it from any floor `X` (with `1 <= X <= N`).&#x20;

Your goal is to know **with certainty** what the value of `F` is.

What is the minimum number of moves that you need to know with certainty what `F` is, regardless of the initial value of `F`?

**Example 1:**

```
Input: K = 1, N = 2
Output: 2
Explanation: 
Drop the egg from floor 1.  If it breaks, we know with certainty that F = 0.
Otherwise, drop the egg from floor 2.  If it breaks, we know with certainty that F = 1.
If it didn't break, then we know with certainty F = 2.
Hence, we needed 2 moves in the worst case to know what F is with certainty.
```

**Example 2:**

```
Input: K = 2, N = 6
Output: 3
```

**Example 3:**

```
Input: K = 3, N = 14
Output: 4
```

**Note:**

1. `1 <= K <= 100`
2. `1 <= N <= 10000`

```java
class Solution {
    // O(K*N*logN)
    public int superEggDrop(int K, int N) {
        // dp[i][j] -> min tests required with i eggs and j floors
        int[][] dp = new int[K + 1][N + 1];
        // Base cases
        // We need 1 trial for 1 floor and 0 trials for 0 floors
        for (int i = 1; i <= K; i++) {
            dp[i][0] = 0;
            dp[i][1] = 1;
        }
        // We always need j trials with 1 egg and j floors.
        for (int j = 1; j <= N; j++)
            dp[1][j] = j;
        for (int i = 2; i <= K; i++) {
            for (int j = 2; j <= N; j++) {
                // O(N) Linear Search
//                dp[i][j] = Integer.MAX_VALUE;
                // checking the best we can get out of worst case for each floor
//                for (int x = 1; x <= j; x++) {
                // If the egg breaks then we need to consider i-1 eggs and x-1 floors
                // If the egg does not breaks then we need to consider i eggs and j-x floors
//                    int res = 1 + Math.max(dp[i - 1][x - 1], dp[i][j - x]);
//                    dp[i][j] = Math.min(dp[i][j], res);
//                }
                // O(logN) Binary Search
                // We don't need to go over all floors from 1 to j
                // As for a fixed j, dp[i][j] goes up as j increases.
                // This means dp[i-1][x-1] will increase and dp[i][j-x] will decrease as x goes from 1 to j.
                // The optimal value of x will be the middle point where the two meet().
                // So to get the optimal x value for dp[i][j], we can do a binary search for x from 1 to j.
                int low = 1, high = j;
                int result = Integer.MAX_VALUE;
                while (low < high) {
                    int mid = low + (high - low) / 2;
                    int left = dp[i - 1][mid - 1];
                    int right = dp[i][j - mid];
                    result = Math.min(result, Math.max(left, right) + 1);
                    if (left == right)
                        break;
                    else if (left < right)
                        low = mid + 1;
                    else
                        high = mid;
                }
                dp[i][j] = result;
            }
        }
        return dp[K][N];
    }
}
```