Last week’s post presented several variants of the following general problem: you have a number of light bulbs, and you need to determine the highest floor in a building from which a bulb may be dropped without breaking. All light bulbs are identical in that they all have the following properties:
- If a light bulb is dropped from a given floor and breaks, then any other light bulb will also break if dropped from that or any higher floor.
- If a light bulb is dropped from a given floor and does not break, then neither it nor any other light bulb will break if subsequently dropped from that or any lower floor.
- A light bulb may be dropped any number of times until it breaks, after which it is unusable and cannot be dropped again.
A “drop” consists of taking a single light bulb in the elevator up to a particular floor, dropping the light bulb from that floor, taking the elevator back down, and checking whether the dropped light bulb broke.
If the building has floors, and you have light bulbs at your disposal, what is the least number of drops required to guarantee that after at most drops you can determine the highest floor from which a light bulb may be dropped without breaking?
Each variant of the problem from last week simply changed the value of , the number of available light bulbs. The basic idea is most clearly illustrated with the simplest case of ; with just a single light bulb, we can do no better than dropping from floor 1, then floor 2, 3, 4, etc., until the bulb finally breaks, requiring drops in the worst case.
At the other extreme, suppose that we have “plenty” of light bulbs that we can afford to break (i.e., ). In this case, intuition correctly suggests that a binary search is the right approach: for a 100-floor building, start by dropping a light bulb from floor 50. If it breaks, then drop a second bulb from floor 25, otherwise drop the second bulb from floor 75, reducing the number of “candidate” floors by approximately half with each drop. The maximum number of drops required is , or 7 drops in the case of the original interview question from last week:
Problem 1: “Given 20 ‘destructible’ light bulbs (which breaks at certain height), and a building with 100 floors, how do you determine the height that the light bulb breaks?” – Asked at QUALCOMM
As I said last week, I suspect that this question actually contains a typo, since 20 light bulbs is “more than plenty;” we will only ever actually use 7 of them. Things get more interesting if we have a more limited supply of light bulbs to break. In the usual statement of this problem, , and the final variant from last week asked the question for . However, we can tackle all of these variants at once by solving the general case.
The key to the solution is to turn the problem around, so to speak, and solve for instead of . That is, given a maximum number of drops , and a supply of light bulbs, what is the tallest building that we can handle? More precisely, what is the maximum number of floors for which we can guarantee to find the “critical” floor in at most drops?
Consider the first drop from the as-yet-unknown optimal floor . If the bulb breaks, then by Property 1 (and 3) above, there must be at most floors below floor . If the bulb does not break, then by Property 2 (and 3), there must be at most floors above floor . Thus, satisfies the following recurrence relation:
Using the identity
it is not difficult to show that
This gives us a solution to all three original problems. For any given number of floors and number of light bulbs , we simply find the smallest number of drops for which . To answer Problem 2, for example, for a 100-floor building with 2 light bulbs, we need 14 drops in the worst case.
Problem 3: Similarly, with 5 or more light bulbs we can do it in 7 drops… but we must be careful, since a binary search will only work with 7 or more light bulbs. If we only have 5 (or 6) bulbs, the optimal strategy is slightly different. Fortunately, the counting argument above gives a recipe for determining from which floor to drop the next light bulb in any situation: assuming that we have calculated the optimal number of drops remaining, the next drop should be from floor , counting from the lowest remaining “candidate” floor. For example, beginning with 5 light bulbs, the first bulb should be dropped from floor 57. If it breaks, the second bulb is dropped from floor 26. If it also breaks, the third bulb is dropped from floor 11. If it breaks, the fourth bulb is dropped from floor 4. If it breaks, the fifth and final bulb must be dropped from floors 1, 2, and 3 in the worst case, for a total of 7 drops.
Finally, using the identity
we can see how the binary search arises in the case where we have “more than enough” light bulbs.