Ramesh is given **k** identical eggs and has access to a building with n floors labeled from **1** to **n**. He is told that there exists a floor **f ( 0 <= f <= n )** where any egg dropped at a floor higher than f will break, and any egg dropped at or below floor f will not break.

For each move, Ramesh may take an unbroken egg and drop it from any floor

**x**, where

**1 <= x <= n**. If the egg breaks, the person can no longer use it, but if the egg does not break, they may reuse it in future moves.

Ramesh is asked to determine with certainty what the value of

**f**is, using minimum number of moves.

###### Solution:

This Egg Dropping Problem and can be solved using **dynamic programming**. The idea is to find the minimum number of moves needed to determine the floor f where the egg will break, using the minimum number of eggs.

We can start by defining a two-dimensional array dp[n+1][k+1], where dp[i][j] represents the minimum number of moves required to determine the floor f with i floors and j eggs.

We can start with the base case where there is only one egg, and we have to determine the floor f with i floors. In this case, we can use a linear search approach by dropping the egg from each floor one by one, starting from the first floor. This will take i moves to determine the floor f.

If we have more than one egg, we can start by dropping the egg from the middle floor x, where x = n/2. If the egg breaks, we can reduce the problem to determining the floor f in the lower half of the building, with one less egg. If the egg does not break, we can reduce the problem to determining the floor f in the upper half of the building, with the same number of eggs.

Using this approach, we can formulate the following recurrence relation for dp[i][j]:

dp[i][j] = 1 + min(max(dp[x-1][j-1], dp[i-x][j])) for x in range(1, i+1)

dp[x-1][j-1] represents the number of moves required to determine the floor f in the lower half of the building with x-1 floors and j-1 eggs

dp[i-x][j] represents the number of moves required to determine the floor f in the upper half of the building with i-x floors and j eggs.

The max function represents the worst-case scenario, as we need to find the floor f where the egg will break in the minimum number of moves, regardless of the outcome of the drop.

The final solution to the problem is dp[n][k], which represents the minimum number of moves required to determine the floor f with n floors and k eggs.

**Tabulation:**

def eggDrop(n: int, k: int) -> int: # Create a 2D array to store the minimum attempts for a given number of eggs and floors dp = [[0] * (k + 1) for _ in range(n + 1)] # Loop over each egg and floor for i in range(1, n + 1): for j in range(1, k + 1): # If we have only one egg, we need to try every floor up to k if i == 1: dp[i][j] = j # If we have only one floor, we only need one attempt elif j == 1: dp[i][j] = 1 else: # Set the minimum attempts to infinity dp[i][j] = float('inf') # Try dropping the egg from every floor up to j for x in range(1, j + 1): # We have two possibilities: # 1. The egg breaks, so we need to check the lower floors with one less egg # 2. The egg doesn't break, so we need to check the higher floors with the same number of eggs # We take the maximum of these two possibilities since we want to minimize the worst-case scenario res = 1 + max(dp[i - 1][x - 1], dp[i][j - x]) # Update the minimum attempts dp[i][j] = min(dp[i][j], res) # Return the minimum attempts for n eggs and k floors return dp[n][k] # Test the function k = 2 n = 10 print("Minimum number of moves required [k = 2, n = 10]:", eggDrop(k, n)) k = 2 n = 36 print("Minimum number of moves required [k = 2, n = 36]:", eggDrop(k, n))

Output:

Minimum number of moves required [k = 2, n = 10]: 4 Minimum number of moves required [k = 2, n = 36]: 8

**Memoization:**

def eggDrop(n: int, k: int, memo = {}) -> int: """ A function that returns the minimum number of moves required to determine the floor f from which an egg will break, using k identical eggs and a building with n floors. Parameters: n (int): The number of floors in the building. k (int): The number of identical eggs available. memo (dict): A dictionary to store the results of subproblems already solved. Returns: int: The minimum number of moves required to determine the floor f from which an egg will break. """ # Base case if there is only 1 egg if k == 1: return 1 # Base case if there is only 1 floor if n == 1: return k # Check if the result of subproblem already exists in memo if (n, k) in memo: return memo[(n, k)] # Initialize the minimum number of moves to a large number min_val = float('inf') # Try dropping the egg from each floor from 1 to k for i in range(1, k + 1): # Calculate the worst-case number of moves required for each floor res = 1 + max(eggDrop(n - 1, i - 1, memo), eggDrop(n, k - i, memo)) # Choose the floor which results in the minimum number of moves min_val = min(min_val, res) # Store the result of subproblem in memo memo[(n, k)] = min_val # Return the minimum number of moves return min_val # Test the function k = 2 n = 10 print("Minimum number of moves required [k = 2, n = 10]:", eggDrop(k, n)) k = 2 n = 36 print("Minimum number of moves required [k = 2, n = 36]:", eggDrop(k, n))

Output:

Minimum number of moves required [k = 2, n = 10]: 4 Minimum number of moves required [k = 2, n = 36]: 8

The time complexity of the algorithm is O(n^2*k), as we need to fill the two-dimensional array dp[n+1][k+1]. The space complexity of the algorithm is also O(n^2*k), as we need to store the intermediate results in the array dp[n+1][k+1].