Egg Dropping Problem

Algorithms

The Egg Dropping problem finds the minimum number of attempts needed to determine the highest floor from which an egg can be dropped without breaking, given $k$ eggs and $n$ floors.

Problem Statement

Given $k$ eggs and $n$ floors, find the minimum number of attempts needed in the worst case to find the critical floor.

Dynamic Programming Solution

We use dynamic programming where $d p [i] [j]$ represents the minimum attempts needed with $i$ eggs and $j$ floors.

Time Complexity

The time complexity is $O (k \times n^{2})$ , where $k$ is the number of eggs and $n$ is the number of floors.

Implementation

def egg_dropping(k, n):
    """Dynamic Programming approach to solve the Egg Dropping Problem."""
    # Create a table to store results of subproblems
    dp = [[0] * (n + 1) for _ in range(k + 1)]
    
    # If we have only one egg, we need n attempts for n floors
    for i in range(1, n + 1):
        dp[1][i] = i
    
    # If we have zero floors, we need zero attempts
    # If we have one floor, we need one attempt
    for i in range(1, k + 1):
        dp[i][0] = 0
        dp[i][1] = 1
    
    # Fill the dp table for all eggs and floors
    for i in range(2, k + 1):
        for j in range(2, n + 1):
            dp[i][j] = float('inf')
            for x in range(1, j + 1):
                worst_case = 1 + max(dp[i-1][x-1], dp[i][j-x])
                dp[i][j] = min(dp[i][j], worst_case)
    
    return dp[k][n]

# Example usage:
k = 2  # Number of eggs
n = 10 # Number of floors
print("Minimum number of attempts needed: {}".format(egg_dropping(k, n)))  # Output: 4