Bulb 1: drop from the Xth floor, then the 2Xth floor, 3Xth floor, and so on until you pass 100. The bulb will survive a drop from the AXth floor, but break on the (A+1)Xth floor. For X = 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16 the worst case number of drops is floor(100/X) = 50, 33, 25, 20, 16, 14, 12, 11, 10, 9, 8, 7, 7, 6, 6. This narrows the break point to a range of values between AX+0.5 and (A+1)X - 0.5, and leaves X-2 floors whose result must be found.
Bulb 2: iterate over the X-2 unknown floors checking them too. Worst case performance is X-2 further tests. Total worst case performance is floor(100/X) + X - 2 = 50, 34, 27, 23, 20, 19, 18, 18, 18, 18, 18, 18, 19, 19, 20.
So pick X = 8, 9, 10, 11, 12 or 13. For example, drop the first bulb from floors 8, 16, 24, 32, 40, 48, 56, 64, 72, 80, 88 and 96. Worst case scenario is the bulb survives being dropped from floor 88 but breaks when dropped from floor 96. That's 12 drops.
Drop the second bulb from floors 89, 90, 91, 92, 93, 94 and 95. Worst case scenario is the bulb survives being dropped from floor 94 and breaks/survives when dropped from floor 95. That's 6 more drops.
Total is 18 drops.
The problem with this question is that you could just randomly pick 10 and find the right answer without having to do any calculation. Meh.
Ah, I see now though that if the bulb passes at 8 then you have reduced the problem to a 92-storey building so the "step size" upwards should be reduced. You don't even need to do that to get a good answer though. Ridiculous.
For 100 storeys, you drop the first bulb at floors 9, 22, 34, 45, 55, 64, 72, 79, 85, 90, 94, 97, 99 and 100. If the first bulb breaks, iterate over the gap that's left over. Worst case is 14 drops total.
"The problem with this question is that you could just randomly pick 10 and find the right answer without having to do any calculation. Meh."
True, but consider it as a test of intuition. Why pick 10? Because it is √100 (or maybe because it is log(100)). The intuitive approach doesn't get you the perfect answer, but it gets you into the ballpark.
Having picked 10, we might then realise that the 'worst case' changes and gets worse the higher up the building we go, so then intuition might say that we need to tweak the step size somehow to get down the size of the worst case. Or we might think that that step size works fine for a 100 storey building, but what about a 10,000 storey building? Our intuition is telling us the algorithm can still be refined.
But then maybe we look at what you wrote and think to ourselves, 'what if the best sequence isn't linear, but is based off the fibonacci sequence instead?'. And then maybe we tootle around a bit with our theoretical fibonacci based algorithm. Maybe we decide it isn't quite as good because it has a worse worse case. But then we might have another intuition, that perhaps there are other ways of measuring which is the better algorithm. So lets say we measure the average, and lo and behold the theoretical fibonacci algorithm has a better average, but a worse worst case. We might be confused at that point as to which one was 'better', because they are each better by different measures. But now we can put it into a broader context and reason about which one to use in which situation.
Moreover recognising that this sort of problem can be decomposed into smaller chunks is not a bad thing. Having a good intuition towards decomposition is an important part of design.
Bulb 1: drop from the Xth floor, then the 2Xth floor, 3Xth floor, and so on until you pass 100. The bulb will survive a drop from the AXth floor, but break on the (A+1)Xth floor. For X = 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16 the worst case number of drops is floor(100/X) = 50, 33, 25, 20, 16, 14, 12, 11, 10, 9, 8, 7, 7, 6, 6. This narrows the break point to a range of values between AX+0.5 and (A+1)X - 0.5, and leaves X-2 floors whose result must be found.
Bulb 2: iterate over the X-2 unknown floors checking them too. Worst case performance is X-2 further tests. Total worst case performance is floor(100/X) + X - 2 = 50, 34, 27, 23, 20, 19, 18, 18, 18, 18, 18, 18, 19, 19, 20.
So pick X = 8, 9, 10, 11, 12 or 13. For example, drop the first bulb from floors 8, 16, 24, 32, 40, 48, 56, 64, 72, 80, 88 and 96. Worst case scenario is the bulb survives being dropped from floor 88 but breaks when dropped from floor 96. That's 12 drops.
Drop the second bulb from floors 89, 90, 91, 92, 93, 94 and 95. Worst case scenario is the bulb survives being dropped from floor 94 and breaks/survives when dropped from floor 95. That's 6 more drops.
Total is 18 drops.
The problem with this question is that you could just randomly pick 10 and find the right answer without having to do any calculation. Meh.