EPTwow, now thats a sentence you can justifiyable rip me for how little sense it makes
Interesting maths problem - Page 3
| Blogs > MakkurtE |
|
MakkurtE
United States46 Posts
wow, now thats a sentence you can justifiyable rip me for how little sense it makes | ||
|
igotmyown
United States4291 Posts
+ Show Spoiler + 10+9+8+7+6+5+4+1=50 | ||
|
gzealot
Singapore238 Posts
if both eggs are breakable start from half the max height and towards the max floor. Every iteration, divide the search space by two and drop the egg from that floor. Once the first egg breaks, u know the the max floor on which the egg is breakable is in between the last known safe floor and the floor which the egg broke on. then u run a linear search from the last known safe floor to find the actual number. Or for an amortized best worst-case algorithm, use steps of sqrt(maxfloor) for your first egg, and when the first egg breaks, run linear search on the second egg. i.e. you have 50 stories, and the egg breaks on 37 floor. Then u would test in this order: 1st egg: 25 -> 37 (oops the egg breaks!) 2nd egg: 26,27,28,29,30,31,32,33,34,35,36,37(breaks, therefore the egg's value is 36) There isnt any real shortcut to this problem. | ||
|
MakkurtE
United States46 Posts
| ||
|
gzealot
Singapore238 Posts
| ||
|
Cloud
Sexico5880 Posts
It's an interview question ffs. Even if you could use pen and paper, you have only 2 eggs. Binary search is way too risky. | ||
|
EsX_Raptor
United States2802 Posts
| ||
|
starfries
Canada3508 Posts
| ||
|
2on2
United States142 Posts
Imo if your drop @ 50 and it doesnt break..done..but its an egg and it will break @ 1 so... But its a math problem and Im no genious so I cant be right | ||
|
Nytefish
United Kingdom4282 Posts
I suppose if you only consider the worst case, triangle numbers win out. The way the question is phrased seems to imply that's what you're looking for too. | ||
|
Hyperionnn
Turkey4968 Posts
+ Show Spoiler + Drop first egg from 10,19,27,34,40,45,49th floor, when your egg broke in floor 34, then drop your 2nd egg starting with 28 and going on, so my answer is 10 #2 + Show Spoiler + 8^3=512 | ||
|
Kiarip
United States1835 Posts
On November 11 2009 06:44 gyth wrote: Are there any non zero solutions to that equation? Yeah there are. for example: (26,30) | ||
|
gyth
657 Posts
y^2 = (4y +4x +1)(y -x) x^2 = (3y +3x +1)(y -x) | ||
|
Luddite
United States2315 Posts
25, 38, 44, 47, 49, 50. That's 6 drops, assuming no breaks. If there's a break somewhere, just search in between that range in the same way. i don't know why people are trying to make this so difficult, and saying 10. | ||
|
Impervious
Canada4217 Posts
On November 13 2009 14:12 Luddite wrote: #1+ Show Spoiler + 25, 38, 44, 47, 49, 50. That's 6 drops, assuming no breaks. If there's a break somewhere, just search in between that range in the same way. i don't know why people are trying to make this so difficult, and saying 10. What if it breaks on 25, then breaks on 12/13 (whichever you choose to drop on)? How do you find out what floor it really breaks on then? You only have 2 eggs to drop. If the first one breaks on 25, you have to do a linear search from 1-24. That's a potential for 25 drops. The 10 drop method will find it in 10 drops or less. | ||
|
imDerek
United States1944 Posts
This is also generalizable to if you're given an arbitrarily number of eggs E, then the number of drops required is O(N^(1/E)) | ||
|
Jonoman92
United States9109 Posts
On November 13 2009 15:52 imDerek wrote: if you have two eggs, then you should drop the first egg in a way such that it only takes roughly sqrt(N) drops to get to floor N, so you can do either f(n) = sqrt(N)*n or f(n) = n^2, the former is better if the answer is close to N, but the latter works better if the answer is small compared to N, so let's say you use the first one, and you broke it at some floor f(k), then you know the answer N' is within f(k-1) < N' <= f(k), so you use the second egg, start from f(k-1)+1, go up by 1 floor each time until you get the right answer. At the worst case (floor 49), this will require 14 drops if we pick f(n) = 7*n (7,14,21,28,35,42,49,43,44,45,46,47,48,49) This is also generalizable to if you're given an arbitrarily number of eggs E, then the number of drops required is O(N^(1/E)) Well done, that seems right to me. | ||
| ||
