The problem
You have two identical crystal balls and you are to determine the most efficient way to figure out the lowest floor in a given building where the crystal balls will break when dropped.
Setting up the problem
If all you had was one crystal ball, the only way to guarantee success in finding the answer would be with a linear search, or simply dropping the ball from each story, starting at the first, until you found the solution. Because we have 2 crystal balls though, we have more freedom to jump around. Suppose that the building in the problem has 120 floors. With a linear search, your worst case scenario would be 120 drops. If you moved in intervals of 2 floors though, your worst case scenario would be 61 steps. 60 steps forward, 1 step backward to see if the previous floor was the breaking point or if the floor at step 60 was the breaking point. If you moved in intervals of 3, your worst case scenario would be 42 steps. 40 steps forward, 1 step backward to the floor above the previous interval and 1 more step forward to complete scanning the entire interval.
To write this out mathematically, you could use use the following variables:
- n = total number of floors
- m = step interval
And the equation would look like this:
n / m + (m - 1) = total number of steps in the worst case
For the example using intervals of 3, the equation would be applied as:
120 / 3 + (3 - 1) => 40 + 2 => 42
So in order to figure out the optimal, or most efficient, interval size, we want to minimize the total number of drops and we can do this by finding the derivative of the function of n / m + (m - 1) which is the square root of n. Another way to find this solution without the use of calculus is to approximate m - 1 as m and set n / m = m. Solve for m, which is also the square root of n.
The solution
Given this minimization, the optimal way to find the lowest floor at which one of the crystal balls would break is by traversing the building in intervals of the square root of n.
Top comments (0)