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\; ~}\frac{1}{2}{t}^2$

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