15th May
2010
written by admin

Here’s a fun problem I took a stab at.

“You have 2 lightbulbs in a 100 story building, the goal is to find the highest floor you can drop a lightbulb from without it breaking.  You can break both lightbulbs in your tests.”

At first this may sound really easy, divide and conquer and then go up by ones to find the solution, after 10 seconds you’ll realize this doesn’t work at all.  My first actual attempt used an algorithm that used fixed steps of 10 to drop the lightbulbs with a worst of 19 when 99 is the answer.  I didn’t like how much worse this got the higher the test so I looked for another solution.  I came up with a method that uses the summation formula to pick the increment of each drop.  New worst case is 14 drops.  Want to see how it works check it out here.

LightBulb Solution