Egg dropping Puzzle in C++

The Egg Dropping Puzzle problem is a well-known problem, which needs dynamic programming to solve optimally. The case of this well-known Puzzle that involves N = 2 eggs and a structure with K = 36 floors is described below.

Consider the situation where we want to determine which floors in a 36-story building are safe to drop eggs from and which will result in the eggs breaking when they land. We assume the following:

• A fallen egg that survives can be utilized once more.
• A cracked egg needs to be thrown away.
• All eggs experience the same effects of a fall.
• An egg would shatter if it were dropped from a higher floor since eggs break when they are dropped.
• An egg would survive a shorter fall if it can survive a fall.
• Both the possibility that eggs are broken by first-floor windows and the possibility that the 36th floor does not break eggs are not excluded.

There is only one way to experiment if there is only one egg available, and we want to ensure that we get the desired outcome. If the egg survives, drop it from the second-floor window after dropping it from the first-floor window. Continue going up until it snaps. In the worst-case scenario, this technique might need 36 droppings.

Finding the key floor is not the issue at hand; rather, the issue is deciding which floors eggs should be dropped from in order to reduce the overall Number of attempts. In this post, we'll talk about a general solution to the problem of 'N' eggs and 'K' floors.

Approach 1: Egg Dropping Puzzle using Recursion:

• Try dropping an egg from each floor (from 1 to K) to get the minimum number of drops required in the worst-case scenario. A component of the solution will be the floor that provides the least value under the worst-case scenario.
• The worst-case minimum number of trials is returned in the following solutions, and these solutions can be changed to output the trial floor numbers as well.

What is the worst-case scenario?

The user is guaranteed to be on the threshold floor in the worst-case situation. For instance, if we have "1" egg and "K" floors, we shall drop the egg from the first floor until it breaks, assuming it does on the "Kth" floor. Hence, the Number of trials to provide us with certainty is "K".

Optimal Substructure:

When we drop an egg from floor x, there can be two cases (1) The egg breaks (2) The egg doesn't break.

1. As some floors should exist lower than "x" in which the egg would not break, if the egg breaks after falling from "xth" floor, we need to check for floors lower than "x" with remaining eggs. As a result, the problem is reduced to x-1 floors and n-1 eggs.
2. The problem is reduced to 'k-x' floors and n eggs if the egg doesn't crack after falling from the 'xth' floor, in this case we need to check for floors higher than 'x'. Try dropping an egg from each floor (from 1 to K) to get the minimum number of drops required in the worst-case scenario. A component of the solution will be the floor that provides the least value under the worst-case scenario.

We only pick a maximum of two cases because we need to reduce the Number of trials in the worst-case scenario. We take into account the maximum of the two situations above for each level and select the floor that results in the fewest trials.

Example:

Let us take an example to illustrate the Egg Dropping Puzzle in C++ using Recursion.

Output:

Complexity Analysis:

Time Complexity: The time complexity of this program is exponential because overlapping subproblems are present.

Auxiliary Space: The space complexity is O(1) because no data structure was used to store values.

Approach 2: Egg Dropping Puzzle using Dynamic Programming:

This problem has the Overlapping Subproblems attribute because the same subproblems are called repeatedly. Therefore, the Egg Dropping Puzzle contains both characteristics of a dynamic programming issue. Recomputations of the same subproblems can be avoided, like with other common Dynamic Programming (DP) problems, by building a temporary array eggFloor[][] from the bottom up.

Formally, for completing DP[i][j] state, where 'i' is the number of eggs and 'j' is the number of floors:

For each floor 'x', we must travel from '1' to 'j' and discover at least:

Example:

Let us take another example to illustrate the Egg Dropping Puzzle in C++ using Dynamic Programming.

Output:

Complexity Analysis:

Time Complexity: The time complexity is O(N * K2). As we use a nested for loop 'k^2' times for each egg

Auxiliary Space: The time complexity is O(N * K). A 2-D array of size n*k is used for storing elements.

Approach 3: Egg Dropping Puzzle using Memoization:

In the first recursive technique, we can utilize a 2D dp table to record the outcomes of overlapping subproblems, which will assist in lowering the time complexity from exponential to quadratic.

dp table state -> dp[i][j], where 'i' denotes the quantity of eggs and 'j' denotes the quantity of floors:

Follow the below steps to solve the problem:

• Create a 2-D array memo with the size N+1 * K+1 and then call the solveEggDrop(N, K) function.
• Return memo[n][k] if memo[N][K] has already been calculated.
• Return K if K == 1 or K == 0 (Base Case).
• Return K if N equals 1 (base case).
• Create an integer res and an integer min that are both equal to the integer Maximum.
• From x equal to 1 until x is less than or equal to K, run a for loop.
  • Set res equal to maximum of solveEggDrop(N-1, x-1) or solveEggDrop(N, k-x)
  • If res is less than integer min then set min equal to res
• Set memo[N][K] equal to min + 1
• Return min + 1.

Example:

Let us take another example to illustrate the Egg Dropping Puzzle in C++ using Memoization.

Output:

Complexity Analysis:

Time Complexity: O(n*k*k) where n is Number of eggs and k is Number of floors.

Auxiliary Space: O(n*k) as 2D memoisation table has been used.

Approach: 4

To solve the problem follow the below concept:

It has been mentioned before how to use a method with O(N * K2), where dp[N][K] = 1 + max(dp[N - 1][i - 1], dp[N][K - i]) for i in 1...K. We thoroughly investigated every option in that strategy.

dp[m][x] denotes the maximum Number of levels that can be checked with x eggs and m moves.

Follow the below steps to solve the problem:

• Declare a 2-D array of size K+1 * N+1 and an integer m equal to zero
• While dp[m][n] < k
  • Increase 'm' by 1 and run a for loop from x equal to one till x is less than or equal to n.
  • Set dp[m][x] equal to 1 + dp[m-1][x-1] + dp[m-1][x].
• Return m.

Example:

Let us take another example to illustrate the Egg Dropping Puzzle in C++.

Output:

Complexity Analysis:

Time Complexity: The time complexity is O(N * K).

Auxiliary Space: The space complexity is O(N * K).

Approach 5: Egg Dropping Puzzle using space-optimized DP:

In this method, the method can be improved to 1-D DP because we only need the data from the previous row to calculate the current row of the DP table and nothing more.

To solve the issue, follow the instructions listed below:

• Make a N+1-sized array dp and an integer m.
• Run a for loop from m = 0 to dp[n] k.
• From x equal to n until x is greater than zero, execute a nested for loop.
• dp[x] should be set to 1 + dp[x-1].
• Return m

Example:

Let us take another example to illustrate the Egg Dropping Puzzle in C++ using space-optimized DP.

Output:

Time Complexity: The time complexity is (N * log K).

Auxiliary Space: The space complexity is O(N).