Taro Logo

Egg Drop With 2 Eggs and N Floors

Medium
Disney logo
Disney
0 views
Topics:
Dynamic ProgrammingArrays

You are given two identical eggs and you have access to a building with n floors labeled from 1 to n.

You know that there exists a floor f where 0 <= f <= n such that any egg dropped at a floor higher than f will break, and any egg dropped at or below floor f will not break.

In each move, you may take an unbroken egg and drop it from any floor x (where 1 <= x <= n). If the egg breaks, you can no longer use it. However, if the egg does not break, you may reuse it in future moves.

Return the minimum number of moves that you need to determine with certainty what the value of f is.

Example 1:

Input: n = 2
Output: 2
Explanation: We can drop the first egg from floor 1 and the second egg from floor 2.
If the first egg breaks, we know that f = 0.
If the second egg breaks but the first egg didn't, we know that f = 1.
Otherwise, if both eggs survive, we know that f = 2.

Example 2:

Input: n = 100
Output: 14
Explanation: One optimal strategy is:
- Drop the 1st egg at floor 9. If it breaks, we know f is between 0 and 8. Drop the 2nd egg starting from floor 1 and going up one at a time to find f within 8 more drops. Total drops is 1 + 8 = 9.
- If the 1st egg does not break, drop the 1st egg again at floor 22. If it breaks, we know f is between 9 and 21. Drop the 2nd egg starting from floor 10 and going up one at a time to find f within 12 more drops. Total drops is 2 + 12 = 14.
- If the 1st egg does not break again, follow a similar process dropping the 1st egg from floors 34, 45, 55, 64, 72, 79, 85, 90, 94, 97, 99, and 100.
Regardless of the outcome, it takes at most 14 drops to determine f.

Constraints:

  • 1 <= n <= 1000

Solution


Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

  1. What are the possible ranges for the number of floors (N)? Can N be zero or negative?
  2. If an egg breaks at floor 'x', does that imply it would also break at all floors above 'x'?
  3. If an egg doesn't break at floor 'x', does that imply it wouldn't break at any floor below 'x'?
  4. What is the desired output? Is it the minimum number of drops to *guarantee* finding the critical floor, or the expected number of drops?
  5. If it's impossible to determine the critical floor with the given number of eggs and floors, what should I return? For example, should I return -1 or throw an exception?

Brute Force Solution

Approach

The brute force approach to the egg drop problem is like trying every single floor as the first drop point. We want to find the worst-case scenario for each of these starting floors and then pick the best one from those worst cases.

Here's how the algorithm would work step-by-step:

  1. Imagine dropping the first egg from the first floor.
  2. If it breaks, you only have one egg left, so you need to try each floor below one-by-one, starting from the first floor.
  3. If the first egg doesn't break on the first floor, you can try dropping it from the second floor, then the third, and so on, until the top floor.
  4. For each floor you try as the first drop, figure out the worst-case scenario, meaning the maximum number of drops you might need to find the critical floor.
  5. After evaluating the worst case scenario for each starting floor, choose the starting floor that results in the smallest number of drops in its worst case.
  6. That smallest number of drops is the answer.

Code Implementation

def egg_drop_brute_force(number_of_floors):
    minimum_number_of_drops = float('inf')

    for floor_to_try_first in range(1, number_of_floors + 1):
        # Calculate the worst-case number of drops for starting at this floor
        worst_case_drops_for_floor = 0

        # If the egg breaks on the first drop, we have to check all lower floors one by one.
        if floor_to_try_first > 1:
            worst_case_drops_for_floor = floor_to_try_first - 1

        # If the egg does not break on the first drop we still need to account for
        # the drop that was just performed
        eggs_do_not_break = number_of_floors - floor_to_try_first + 1

        if eggs_do_not_break > worst_case_drops_for_floor:
            worst_case_drops_for_floor = eggs_do_not_break

        # Update the overall minimum if this floor's worst case is better.
        if worst_case_drops_for_floor < minimum_number_of_drops:
            minimum_number_of_drops = worst_case_drops_for_floor

    return minimum_number_of_drops

Big(O) Analysis

Time Complexity
O(n²)The algorithm iterates through each floor from 1 to n as a potential first drop. For each of these floors, in the worst case (where the egg breaks), it then iterates through all floors below it one by one to find the critical floor. Therefore, for each floor i, we might need to perform i drops in the worst case. This results in a sum of 1 + 2 + ... + n, which is equivalent to n(n+1)/2. This simplifies to O(n²).
Space Complexity
O(1)The described approach iterates through possible starting floors but does not store any intermediate results or use any data structures that scale with the number of floors, N. The variables used to track the current floor being tested and the minimum number of drops found so far require constant space. Therefore, the auxiliary space used by this algorithm remains constant regardless of the value of N. The space complexity is O(1).

Optimal Solution

Approach

The goal is to find the highest floor from which an egg won't break, minimizing the worst-case number of drops. The key insight is to make each drop potentially eliminate an equal number of floors below, gradually narrowing down the possibilities.

Here's how the algorithm would work step-by-step:

  1. Start by dropping the first egg from a strategically chosen floor. This floor should be high enough to give information but low enough to not eliminate too many floors in a first break.
  2. If the first egg breaks, we need to test floors below it one by one, using the second egg to find the highest safe floor in that range.
  3. If the first egg doesn't break, we can move up to a higher floor, but not by the same number of floors as before. The next floor should be a smaller increment than the first one. The increments keep getting smaller because, in the worst case, if the first egg breaks at a later drop, the remaining range for the second egg must be shorter to balance things out.
  4. Continue this process of dropping the first egg, incrementing by decreasing amounts each time, until either the egg breaks or you've reached the top floor.
  5. If the first egg breaks at any point, use the second egg to check the floors below the previous drop point one by one to find the highest safe floor.
  6. By decreasing the increments, you are balancing the number of drops needed in the worst-case scenario (egg breaks early versus egg breaks late). This minimizes the maximum number of drops you might need to make.

Code Implementation

def egg_drop(number_of_floors):
    increment_value = 1
    total_drops = 0
    current_floor = 0

    # Determine drops in worst case
    while current_floor < number_of_floors:

        total_drops += 1
        current_floor += increment_value

        increment_value += 1

    return total_drops

def egg_drop_two_eggs(number_of_floors):
    drops_needed = 0
    increment = 1

    #Determines the minimum number of drops.
    while number_of_floors > 0:
        number_of_floors -= increment
        increment += 1
        drops_needed += 1

    return drops_needed

def egg_drop_two_eggs_detailed(number_of_floors):
    drops_needed = 0
    increment_value = egg_drop(number_of_floors) # Initial Increment Calculation
    current_floor = 0

    while current_floor < number_of_floors:
        drops_needed += 1
        current_floor += increment_value

        # Egg breaks, test floors below. 
        if current_floor > number_of_floors:
            drops_needed += (current_floor - number_of_floors) #worst case linear search
            break

        increment_value -= 1

    return drops_needed

Big(O) Analysis

Time Complexity
O(sqrt(n))The algorithm strategically drops the first egg from increasing floors. The increments decrease such that the sum of the increments is approximately equal to n (the total number of floors). Because the increments decrease linearly, this process involves approximately the square root of n drops for the first egg. In the worst case, the first egg breaks on the last of these drops, requiring at most sqrt(n) drops of the second egg to check the remaining floors below, which gives us a time complexity of O(sqrt(n)).
Space Complexity
O(1)The described algorithm uses a constant amount of extra space. It primarily involves iterative calculations and comparisons without the creation of auxiliary data structures like lists, arrays, or hash maps. The space needed for variables to track the current floor being tested and potentially the number of drops remains constant irrespective of the number of floors N. Therefore, the space complexity is O(1).

Edge Cases

CaseHow to Handle
N = 0 floorsReturn 0 because no drops are needed for 0 floors.
N = 1 floorReturn 1 because a single drop on the first floor determines the critical floor.
Two eggs and very large N (e.g., N > 10000)Ensure the algorithm's space and time complexity remain within acceptable bounds, avoiding excessive memory usage or slow execution.
Integer overflow when calculating the drop intervalUse appropriate data types (e.g., long) or techniques to prevent integer overflows during calculations.
Critical floor is the first floorThe algorithm should correctly identify this case and return 1.
Critical floor is the Nth floorThe algorithm should correctly identify this case and return the minimum number of drops needed in the worst case.
No critical floor exists (egg never breaks)Handle this case by correctly reporting the number of drops when the first egg breaks on the Nth floor.
N is negativeTreat this as an invalid input and return an error or a default value like -1.