You have two identical crystal orbs. Your goal is to figure out how high a floor an orb can fall from a 100 story building before it breaks. What is the largest number of orb-drops you would ever have to do to find the right floor (i.e. what is the most efficient strategy by a worst-case measure)? You can break both orbs in your search, provided you yield a unique and correct answer. By former employer Mark Gorton.
Crystal orbs - 3
|
3 Comments ↓
Start at 1/3 of the building – floor 34.
If the 1st ball breaks, start from the bottom. You need 1+33 tries.
If the 1st ball doesn’t break, start going up by two floors. Once the ball breaks, use the second one on the floor below. You need 1+32+1 tries, assuming no ball can survive a drop from the 100th floor (after floor 98 test 99 instead of 100).
There is an even better solution. Hint: your algorithm does something unnecessary. What is it?
(Hope you still look at too old records. :-) )
Start at the square root of the floors number – 10.
If the first ball breaks, start from the bottom. You will find the answer in at most 10 attempts total.
If the first ball doesn’t break, move the same number of floors up, to floor 20. If the ball breaks, start from floor 11. You will have the answer in at most 11 attempts total.
If the first ball doesn’t break, move again 10 floors up. In the worst case scenario, you will find the answer in 19 attempts.
Desire to speak? ↓