Algorithms for Coding Interviews in Python/

...

/

Solution: Egg Dropping Problem

Solution: Egg Dropping Problem

This review provides a detailed analysis of the different ways to solve the egg dropping problem.

We'll cover the following...

Solution 1: brute force

from decimal import Decimal  # Decimal library to assign minimum/maximum numbers
def egg_drop(eggs, floors):
    """
    Figures out which floor of the skyscraper that the eggs can be safely dropped from without breaking.
    :param eggs: Number of stories of the skyscraper
    :param floors: Number of eggs
    :return: Return the floor
    """
    # If there are no eggs, then there can't be any tries
    if eggs <= 0:
        return 0
    # If there are no floors, then no trials needed. OR if there is
    # one floor, one trial needed.
    if floors == 1 or floors == 0:
        return floors
    # We need k trials for one egg and k floors
    if eggs == 1:
        return floors
    
    min = Decimal("Infinity")
    res = 0
    # Consider all droppings from 1st floor to kth floor and
    # return the minimum of these values plus 1.
    for i in range(1, floors + 1):
        res = max(egg_drop(eggs - 1, i - 1), egg_drop(eggs, floors - i))
        if res < min:
            min = res
    return min + 1
# Driver code to test the above function
if __name__ == '__main__':
    
    print(egg_drop(2, 13))

Explanation

When we drop an egg from the floor i, there can be two cases: (1) The egg breaks (2) The egg doesn’t break.

  1. If the egg breaks after dropping from the ithi^{th} floor, then, we only need to check for floors lower than i with remaining eggs; so the problem reduces to i - 1 floors and n - 1 eggs.
  2. If the egg doesn’t break after dropping from the ithi^{th}
...