Nothing special here. It’s just a blog post for summarising my algorithm learning course.

# Question

Suppose that you have an nnn-story building (with floors 1 through nnn) and plenty of eggs. An egg breaks if it is dropped from floor T or higher and does not break otherwise. Your goal is to devise a strategy to determine the value of T given the following limitations on the number of eggs and tosses

# Solution 1

1 egg, ≤T tosses

This is an O(n) solution. Just do a simple loop from the first floor until the egg break.

# Solution 2

∼1lgN eggs, ∼1lgN tosses

Use Binary search strategy.

• Start from the middle floor, drop the egg
• If it breaks, repeat with the lower half
• Otherwise, repeat with the upper half

# Solution 3

∼lgT eggs, ∼2lgT tosses

• Drop the at floor 1, 2, 4, 8, 16,… until it breaks
• If the egg drop at level 32, that mean T must be between 16 and 32 (between the floor of last toss and the floor of this toss). At this time, you have used
• 1 egg
• lgT tosses because you double the floor number each time
• Perform a binary search from floor 16 to 32.
• The binary search will cost another lgT tosses
• Because you do binary search on half of the floor (16 to 32 in this case, not all 32 floors), you need to use lgT - 1 eggs.
• In total, it will take you ~lgT eggs and ~2lgT tosses.

# Solution 4

2 eggs, 2$\sqrt{n}$ tosses

To make it easy to imagine, let’s take n = 100, so $\sqrt{n}$ = 10

• Drop the egg at $\sqrt{n}$ floor (level 10 in this case)
• If it doesn’t break, increase the floor by $\sqrt{n}$ and repeat until the egg breaks
• Until that, you have used maximum $\sqrt{n}$ = 10 tosses and 1 egg
• Now you know the range that can make egg break. That range size is $\sqrt{n}$
• For example, the egg breaks at the floor 60, that mean T must be between 50 and 60
• Do a sequential search in that range, use the other remaining egg. Because the length of that range is $\sqrt{n}$, it takes you maximum another $\sqrt{n}$ = 10 tosses
• The total running time is 2$\sqrt{n}$ and takes 2 eggs

# Solution 5

2 eggs, $\mathrm{\le c}\sqrt{T}$ tosses

I still haven’t thought of the solution for this. Here is the hint that Coursera gave me

$\mathrm{1 + 2 + 3 + ... + t ~}\phantom{\rule{0ex}{0ex}}\frac{1}{2}{t}^{2}$

Aim for $\mathrm{c = 2}\sqrt{2}$