> 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`). 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]; } } ``` --- # Agent Instructions This documentation is published with GitBook. GitBook is the documentation platform designed so that both humans and AI agents can read, navigate, and reason over technical content effectively. Learn more at gitbook.com. ## Querying This Documentation If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question. Perform an HTTP GET request on the current page URL with the `ask` query parameter, and the optional `goal` query parameter: ``` GET https://mayanktyagi3111.gitbook.io/interview-prep/dynamic-programming/egg-dropping-puzzle.md?ask=&goal= ``` `ask` is the immediate question: it should be specific, self-contained, and written in natural language. `goal` is optional and describes the broader end goal you are ultimately trying to accomplish on behalf of the user. GitBook uses it to tailor the answer towards what is most useful for that goal. The response will contain a direct answer to the question and relevant excerpts and sources from the documentation. Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.