1884. Egg Drop With 2 Eggs and N Floors
Problem Explanation:
In this problem, we are given two identical eggs and a building with n floors (numbered 1 to n). We must find the 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. The goal is to find the minimum number of moves required to determine the value of f
with certainty. To solve this problem, we'll be using dynamic programming.
Let's work through an example:
Example
1 2 3Input: n = 2 4Output: 2
For this example, we have 2 floors. 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.
We only needed 2 moves to determine the value of f
, so the output is 2.
Solution Approach
The solution approach for this problem includes using dynamic programming and a 2D array dp
with n + 1
rows and 2 columns, where dp[i][j]
represents the minimum number of moves required to determine the value of f
with i
floors and j + 1
eggs. We will loop over all possible values of j
and get the minimum possible value of dp[i][1]
.
Algorithm Steps
- Create a 2D array
dp
withn+1
rows and 2 columns. - Set
dp[i][0] = i
for all0 <= i <= n
. - Set
dp[1][1] = 1
for a single floor. - For
2 <= i <= n
, if the previous egg was dropped from floorj (1 <= j < i)
, thendp[i][1] = max(dp[j - 1][0], dp[i - j][1]) + 1
. - Loop over all possible values of
j
and get the minimum possible value ofdp[i][1]
. - Finally, return
dp[n][1]
.
Python Solution
1 2python 3class Solution: 4 def twoEggDrop(self, n: int) -> int: 5 def drop(k: int, N: int) -> int: 6 if k == 0: 7 return 0 8 if k == 1: 9 return N 10 if N == 0: 11 return 0 12 if N == 1: 13 return 1 14 if dp[k][N] != -1: 15 return dp[k][N] 16 17 l, r = 1, N + 1 18 19 while l < r: 20 m = (l + r) // 2 21 broken = drop(k - 1, m - 1) 22 unbroken = drop(k, N - m) 23 if broken >= unbroken: 24 r = m 25 else: 26 l = m + 1 27 28 dp[k][N] = 1 + drop(k - 1, l - 1) 29 return dp[k][N] 30 31 dp = [[-1] * (n + 1) for _ in range(3)] 32 return drop(2, n)
Java Solution
1 2java 3class Solution { 4 public int twoEggDrop(int n) { 5 int[][] dp = new int[3][n + 1]; 6 7 for (int i = 0; i <= n; i++) { 8 dp[0][i] = 0; 9 dp[1][i] = i; 10 dp[2][i] = -1; 11 } 12 13 for (int i = 1; i <= n; i++) { 14 int minMoves = Integer.MAX_VALUE; 15 for (int j = 1; j < i; j++) { 16 int moves = Math.max(dp[0][j - 1], dp[1][i - j]) + 1; 17 minMoves = Math.min(minMoves, moves); 18 } 19 dp[2][i] = minMoves; 20 21 if (dp[1][i] == dp[2][i]) { 22 break; 23 } 24 25 dp[1][i] = dp[2][i]; 26 } 27 28 return dp[2][n]; 29 } 30}
JavaScript Solution
1 2javascript 3class Solution { 4 twoEggDrop(n) { 5 const dp = Array.from({length: 3}, () => Array(n + 1).fill(-1)); 6 7 for (let i = 0; i <= n; i++) { 8 dp[0][i] = 0; 9 dp[1][i] = i; 10 } 11 12 for (let i = 1; i <= n; i++) { 13 dp[2][i] = dp[1][i]; 14 for (let j = 1; j < i; j++) { 15 const moves = Math.max(dp[0][j - 1], dp[1][i - j]) + 1; 16 dp[2][i] = Math.min(dp[2][i], moves); 17 } 18 19 if (dp[1][i] === dp[2][i]) { 20 break; 21 } 22 23 dp[1][i] = dp[2][i]; 24 } 25 26 return dp[2][n]; 27 } 28}
C++ Solution
1 2cpp 3class Solution { 4public: 5 int twoEggDrop(int n) { 6 vector<vector<int>> dp(3, vector<int>(n + 1, -1)); 7 8 for (int i = 0; i <= n; i++) { 9 dp[0][i] = 0; 10 dp[1][i] = i; 11 } 12 13 for (int i = 1; i <= n; i++) { 14 dp[2][i] = dp[1][i]; 15 for (int j = 1; j < i; j++) { 16 int moves = max(dp[0][j - 1], dp[1][i - j]) + 1; 17 dp[2][i] = min(dp[2][i], moves); 18 } 19 20 if (dp[1][i] == dp[2][i]) { 21 break; 22 } 23 24 dp[1][i] = dp[2][i]; 25 } 26 27 return dp[2][n]; 28 } 29};
C# Solution
1 2csharp 3public class Solution { 4 public int TwoEggDrop(int n) { 5 int[][] dp = new int[3][]; 6 for (int i = 0; i < 3; i++) { 7 dp[i] = new int[n + 1]; 8 } 9 10 for (int i = 0; i <= n; i++) { 11 dp[0][i] = 0; 12 dp[1][i] = i; 13 dp[2][i] = -1; 14 } 15 16 for (int i = 1; i <= n; i++) { 17 int minMoves = int.MaxValue; 18 for (int j = 1; j < i; j++) { 19 int moves = Math.Max(dp[0][j - 1], dp[1][i - j]) + 1; 20 minMoves = Math.Min(minMoves, moves); 21 } 22 dp[2][i] = minMoves; 23 24 if (dp[1][i] == dp[2][i]) { 25 break; 26 } 27 28 dp[1][i] = dp[2][i]; 29 } 30 31 return dp[2][n]; 32 } 33}
In the solutions above, the logic behind the code in each language is explained step-by-step in the algorithm steps section, as we perform dynamic programming to build up the dp
array and find the minimum number of moves required to determine the value of f
.The solutions above for Python, Java, JavaScript, C++, and C# define the standard dynamic programming method for solving the egg drop problem with two eggs and n floors. These solutions have a time complexity of O(n^2) and O(n) space complexity. You can try implementing the given solutions in your preferred programming language to understand how to solve this problem effectively.
By following the algorithm steps mentioned above and analyzing the code provided for each language, we can better understand the process of problem-solving using dynamic programming. This helps us break down complex problems into simpler sub-problems and solve them in a systematic manner for efficient solutions. Besides, practicing with multiple languages will help you become a better programmer in general, as it strengthens your ability to adapt and learn different programming paradigms.
In conclusion, the egg drop problem is a classic question in dynamic programming that can be solved using various techniques. The methods provided above are well-explained and optimized to solve this problem for given constraints. Implementing the solutions in different programming languages will help you enhance your programming skills and strengthen your understanding of dynamic programming concepts.
How does quick sort divide the problem into subproblems?
Which one best describes the time complexity of the following code?
1int factorial(int n) {
2 if (n < 0) {
3 return -1;
4 } else if (n == 0) {
5 return 1;
6 } else {
7 return n * factorial(n - 1);
8 }
9}
Solution Implementation
What is the best way of checking if an element exists in an unsorted array once in terms of time complexity? Select the best that applies.
Given a sorted array of integers and an integer called target, find the element that
equals to the target and return its index. Select the correct code that fills the
___
in the given code snippet.
1def binary_search(arr, target):
2 left, right = 0, len(arr) - 1
3 while left ___ right:
4 mid = (left + right) // 2
5 if arr[mid] == target:
6 return mid
7 if arr[mid] < target:
8 ___ = mid + 1
9 else:
10 ___ = mid - 1
11 return -1
12
1public static int binarySearch(int[] arr, int target) {
2 int left = 0;
3 int right = arr.length - 1;
4
5 while (left ___ right) {
6 int mid = left + (right - left) / 2;
7 if (arr[mid] == target) return mid;
8 if (arr[mid] < target) {
9 ___ = mid + 1;
10 } else {
11 ___ = mid - 1;
12 }
13 }
14 return -1;
15}
16
1function binarySearch(arr, target) {
2 let left = 0;
3 let right = arr.length - 1;
4
5 while (left ___ right) {
6 let mid = left + Math.trunc((right - left) / 2);
7 if (arr[mid] == target) return mid;
8 if (arr[mid] < target) {
9 ___ = mid + 1;
10 } else {
11 ___ = mid - 1;
12 }
13 }
14 return -1;
15}
16
Recommended Readings
Top Patterns to Conquer the Technical Coding Interview Should the written word bore you fear not A delightful video alternative awaits iframe width 560 height 315 src https www youtube com embed LW8Io6IPYHw title YouTube video player frameborder 0 allow accelerometer autoplay clipboard write encrypted media gyroscope picture in picture
Recursion Recursion is one of the most important concepts in computer science Simply speaking recursion is the process of a function calling itself Using a real life analogy imagine a scenario where you invite your friends to lunch https algomonster s3 us east 2 amazonaws com recursion jpg You first
Runtime Overview When learning about algorithms and data structures you'll frequently encounter the term time complexity This concept is fundamental in computer science and offers insights into how long an algorithm takes to complete given a certain input size What is Time Complexity Time complexity represents the amount of time
Got a question? Ask the Teaching Assistant anything you don't understand.
Still not clear? Ask in the Forum, Discord or Submit the part you don't understand to our editors.