* You are given 2 eggs.
* You have access to a 100-story building.
* Eggs can be very hard or very fragile means it may break if dropped from the first floor or may not even break if dropped from 100 th floor. Both eggs are identical.
* You need to figure out the highest floor of a 100-story building an egg can be dropped without breaking.
* Now the question is how many drops you need to make. You are allowed to break 2 eggs in the process

Why do people say this..



Isn't it a lot more efficient to test on the 50th floor, then 25th or 75th depending if it breaks, diving the floors by 2?
The amount of falls is x, where 2^x > 100 ... x = 7, so a worst case scenario would only require 7 drops. E.g (if egg breaks from 87th floor, one of the worst case scenarios): 50, 75, 88, 81, 84, 86, 87 = 7 drops

This post was edited by Foxic on May 11 2013 02:51am

Keep in mind you don't know what the magic number is yet. you cannot overshoot twice or else you fail to solve the problem.

here's the simplest example:
50 broke
25 broke

so now we know it breaks in the first 25 floors but we don't know which. so we can't solve the problem.

To use your example, you dont know where it breaks yet. that's what you're trying to find out.




so:
50 survive
75 survive
88 broke
81 - what if this broke? then the magic number is somewhere between 76 and 81 and you can't narrow down further.



the simplest way to find where it breaks is to use just 1 egg. start from floor 1 and try dropping it on each floor. clearly you solve the problem, but it's slow. but we need to use this idea.

you must use the first egg to establish a decent upper bound. then you use the second egg to start from the last known good upper bound and go up one at a time. and you jump the upper bound in such a way to optimize it.

This post was edited by carteblanche on May 11 2013 03:03am

I'm probably misunderstanding the questions. Why can't I drop more than 2 eggs using my solution while the other solution may drop up to 14?

This post was edited by Foxic on May 11 2013 03:09am

you can drop it as often as you want, but you can only break 2. so suppose you drop it on floors 50 and 25 and both break. now you have no eggs left. this happened because you overshot twice. but if you read the correct solution, they only overshoot once. after that they undershoot every time until it breaks.

Wow I feel pretty dumb, I see what you mean. Does this mean I'm not cut out for programming?
I normally don't have trouble solving these kinds of puzzles, but I was stumped with this one

This post was edited by Foxic on May 11 2013 03:16am

you misunderstood/misread the problem. what does that have to do with programming ability?

if it makes you feel any better, it took me a while to solve the problem when i heard it years ago. i didn't look up the solution, so i did it by hand. my first strategy was also binary search and i quickly dismissed it. next strategy was to always jump up by 10 floors at a time. then i tried 9 and 11. once i realized i should jump a different amount based on what floor i was on, then the solution was pretty clear.

This post was edited by carteblanche on May 11 2013 03:21am

THROW IT ON THE GROUND! GG LOL

This post was edited by D3HCFTW on May 15 2013 11:25pm

why the fuck are you breaking all my eggs, i need them for breakfast