algorithm - Two marbles and a 100 story building

Question

One of those classic programming interview questions...

You are given two marbles, and told that they will break when dropped from some certain height (and presumably suffer no damage if dropped from below that height). You’re then taken to a 100 story building (presumably higher than the certain height), and asked to find the highest floor your can drop a marble from without breaking it as efficiently as possible.

Extra info

• You must find the correct floor (not a possible range)
• The marbles are both guaranteed to break at the same floor
• Assume it takes zero time for you to change floors - only the number of marble drops counts
• Assume the correct floor is randomly distributed in the building

Answer 1

The interesting thing here is how you can do it in the least amount of drops possible. Going to the 50th floor and dropping the first would be disastrous if the breaking floor is the 49th, resulting in us having to do 50 drops. We should drop the first marble at floor n, where n is the max amount of drops required. If the marble breaks at floor n, we may have to make n-1 drops after that. If the marble doesn't break we go up to floor 2n-1 and if it breaks here we have to drop the second marble n-2 times in the worst case. We continue like this up to the 100th floor and try to break it at 3n-2, 4n-3....
and n+(n-1)+(n-2)+...1 <=100
n=14 Is the maximum drops required