2 Light Bulbs and a 100 Story Building Solution

I’ve been getting quite a bit of traffic to my rant on the 2 light bulbs and 100 story building interview question. To satisfy the curiosity of people coming here for that answer I decided to write a bit about some possible solutions.

There are a number of ways to approach this problem.

100 drops:
The simplest solution to this problem is to start at the first floor and drop a bulb. If the bulb doesn’t break, repeat from the second floor, then the third and so on until the bulb breaks. In the worst case the bulb doesn’t break at all, in which case the bulb would have been dropped 100 times.

1, 2, 3, ..., 98, 99, 100 = Break

 

50 drops:
A slightly better solution is to use binary search. With binary search you split the problem in half at each step, so the first drop would be from the 50th floor. If the bulb doesn’t break the second drop would be from the 75th floor, the third from the 88th floor and so on. If the bulb breaks on the 100th floor it would have been dropped 7 times (floors 50, 75, 88, 94, 97, 99 and 100 always rounding in our favor).

However the worst case with binary search occurs when the bulb breaks on the 49th floor. In this case our first drop breaks the first bulb. After that we can’t afford to break another bulb, as we only have one left. Because we don’t know whether it will break on floor 1 or 49 we have to drop the second bulb from each floor starting with the first, all the way to the 49th. These 49 drops, plus the first drop makes a worst case of 50 drops.

50 = Break
1, 2, 3, ..., 47, 48, 49 = Break

 

44 drops:
Another solution would be to start at the 2nd floor and double the height with each drop

2, 4, 8, 16, 32, 64, 100 = Break
65, 66, 67, ..., 97, 98, 99 = Break

 

25 drops:
You could also make some modifications to the previous strategy. For instance, you could double the floors but limit the maximum increase in height, say to 16 floors. This would get you a maximum of 25 drops. One strength of this method is that it requires fewer drops in the worst case if the breaking height is small, but also scales to larger heights with an acceptable upper bound.

2, 4, 8, 16, 32, 48, 64, 80, 96 = Break
81, 82, 83, 84, 85, 86, 87, 88, 89, 90, 91, 92, 93, 94, 95 = Break

 

19 drops:
Instead of doubling our interval, we could use a fixed size interval. If we increased the height by 10 each time (10, 20, 30…) the worst case would be the bulb breaking at the 99th floor. You can try different intervals, but the best ones are right around 19 drops in the worst case.

10, 20, 30, 40, 50, 60, 70, 80, 90, 100 = Break
91, 92, 93, 94, 95, 96, 97, 98, 99 = Break

 

14 drops:
This solution is the one that your interviewer is looking for. I’m going to explain this one a little bit backward because the examples should help with understanding.

1,   2,  3,  4,  5,  6,  7,  8,  9, 10, 11  <=== Drop #
14, 27, 39, 50, 60, 69, 77, 84, 90, 95, 99  <=== Floor
13, 26, 38, 49, 59, 68, 76, 83, 89, 94, 98  <=== Worst case floor #
13, 12, 11, 10,  9,  8,  7,  6,  5,  4,  3  <=== # of sequential drops
14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14  <=== Total # of drops in worst case

The worst case happens when the bulbs break at floor 13. Our first bulb breaks when we drop it from the 14th floor. Then we have to drop the second bulb one by one until we get to 13 (13 + 1 = 14 drops).

If the bulb doesn’t break after the first drop we can add another 14 floors and drop from the 28th floor just like the 19 drop solution above. However if the bulb breaks at the 27th floor we would have to make 15 drops.

Instead, if we add 13 floors (14 floors – 1 drop), and the first bulb breaks on the 2nd attempt, our worst case is the bulb breaking at the 26th floor. This is still only 14 drops, 2 to break the first light bulb + 12 to break the second.

Continuing on by adding 12 floors we get 3 drops to break the first bulb + 11 to break the second. For every extra drop we use to break the first bulb, we have to decrease the amount of floors to add by one to compensate for that drop.

How do you determine that you should start with 14? It is the first number n where the sum of the numbers 1 through n is greater than 100 (1-14 = 105 vs 1-13 = 91).

 

0 drops:
2 Light Bulbs and a 100 Story Building – The rant that inspired this post which covers some of the problems with this question and a solution in 0 drops.

 

Links

The 2-Lightbulb, 100 Story Building Puzzle by Craig Mason-Jones (pdf)

To learn more about algorithms check out What In The Hell Is Big O or other articles in the What In The Hell Series that cover basic computer science.

Advertisements