Skip to content
This repository has been archived by the owner on Jul 3, 2020. It is now read-only.
/ Egg_problem Public archive

Solution of problem Two eggs and 100 floor building

License

Notifications You must be signed in to change notification settings

Mishco/Egg_problem

Folders and files

NameName
Last commit message
Last commit date

Latest commit

 

History

13 Commits
 
 
 
 
 
 
 
 
 
 
 
 
 
 

Repository files navigation

Egg problem

Classic problem of dynamic programming. Solution of problem Two eggs and 100 floor building

Problem

Suppose that there is a building with 100 floors. You are given 2 identical eggs. Both eggs are identical. The most interesting property of the eggs is that every egg has it’s own “threshold” floor. Let’s call that floor N. What this means is that the egg will not break when dropped from any floor below floor N, but the egg will definitely break from any floor above floor N, including floor N itself.

The aim is to find out the highest floor from which an egg will not break when dropped out of a window from that floor. If an egg is dropped and does not break, it is undamaged and can be dropped again. However, once an egg is broken, that’s it for that egg.

If an egg breaks when dropped from floor n, then it would also have broken from any floor above that. If an egg survives a fall, then it will survive any fall shorter than that.

The question is: What strategy should you adopt to minimize the number egg drops it takes to find the solution?. (And what is the worst case for the number of drops it will take?)

eggs
Figure 1. Eggs afraid of being omelette

Solutions

There are exists multiple possible and good solutions:

Brute force

First solution is brute force (you start at first floor, drop an egg, check it, increase a floor, repeat …​) Time complexity = O(n), and is possible the worst solution, because we probably did not found the best floor.

My solution is binary search (starting in middle, test, on result of test go middle + some value or middle - some value) Time complexity = O(log(n)).

About

Solution of problem Two eggs and 100 floor building

Topics

Resources

License

Stars

Watchers

Forks

Releases

No releases published

Packages

No packages published

Languages