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.

- The binary search will cost another
- 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

- Until that, you have used maximum
- 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**

- For example, the egg breaks at the floor
- 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}$