Egg Dropping Puzzle | DSA in C++ - Software Development PDF Download

Introduction

The egg dropping puzzle is a classic problem in computer science that involves finding the minimum number of attempts required to determine the highest floor from which an egg can be dropped without breaking. In this article, we will explore the solution to this puzzle using dynamic programming in C++. We will provide multiple examples, along with simple code explanations and solutions to sample problems.

Understanding the Problem

Imagine you have 'n' floors in a building and 'k' identical eggs. You need to find the highest floor from which an egg can be dropped without breaking. You can drop an egg from any floor and observe its outcome: either the egg will break or it will remain intact. Your goal is to minimize the number of attempts (drops) required to find the highest safe floor.

Approach

To solve this problem, we will use dynamic programming. We will create a 2D array, 'dp', where 'dp[i][j]' represents the minimum number of attempts required with 'i' floors and 'j' eggs.

Code Implementation:

#include <iostream>

#include <climits>

using namespace std;

int eggDrop(int floors, int eggs) {

    int dp[floors + 1][eggs + 1];

    for (int i = 0; i <= floors; i++) {

        dp[i][0] = 0;  // Zero eggs, zero attempts

        dp[i][1] = i;  // One egg, attempts equal to the number of floors

    }

    for (int j = 0; j <= eggs; j++)

        dp[0][j] = 0;  // Zero floors, zero attempts

    for (int i = 1; i <= floors; i++) {

        for (int j = 2; j <= eggs; j++) {

            dp[i][j] = INT_MAX;

            for (int k = 1; k <= i; k++) {

                int attempts = 1 + max(dp[k - 1][j - 1], dp[i - k][j]);

                dp[i][j] = min(dp[i][j], attempts);

            }

        }

    }

    return dp[floors][eggs];

}

int main() {

    int floors = 10;

    int eggs = 2;

    int minAttempts = eggDrop(floors, eggs);

    cout << "Minimum attempts required: " << minAttempts << endl;

    return 0;

}

Code Explanation:

• We define the 'eggDrop' function that takes the number of floors and eggs as input and returns the minimum attempts required.
• We create a 2D array 'dp' to store the minimum attempts.
• We initialize the base cases: when the number of eggs is 0, the minimum attempts will be 0, and when the number of eggs is 1, the minimum attempts will be equal to the number of floors.
• We fill the remaining entries of the array using nested loops, considering all possible floor drops.
• The 'dp' array is updated with the minimum attempts required for each combination of floors and eggs.
• Finally, we return the minimum attempts stored in 'dp[floors][eggs]'.

Sample Problems

Problem 1: Given 20 floors and 2 eggs, find the minimum number of attempts required.

Minimum attempts required: 6

Problem 2: Given 100 floors and 3 eggs, find the minimum number of attempts required.

Minimum attempts required: 9

Conclusion

In this article, we learned how to solve the egg dropping puzzle using dynamic programming in C++. We explored the approach, provided code implementation, and explained it step by step. By understanding this problem, you can gain insights into dynamic programming techniques and apply them to other similar scenarios.