You have two lightbulbs and a 100-storey building. You want to find the floor at which the bulbs will break when dropped. Find the floor using the least number of drops.

Actually, 16 is not the optimal, nor is 15; you can do it in 14. Here is one solution (there are at least 5 other equivalents): * Drop first bulb at 14th, 27th, 39th, 50th, 60th, 69th, 78th, 85th, 91st, 96th, and (optionally) 100th until it breaks. * Go to the highest floor where the first bulb didn't break. * Repeatedly go up one floor and drop the second bulb. When it breaks, you have your answer. Why is 14 optimal? Since you are decrementing each time, you want (n) such that sum(1..n) barely reaches 100. The answer is n=14. Generally, if the number of floors is (f), the lowest number of drops is ceil((sqrt(8*f+1)-1)/2). This is the best worst-case scenario. An interesting related question is what gives the lowest expected number of drops. And no, I could not have gotten this in an interview.

19 drops is not the best worst case scenario... imagine trying floor 16, if it breaks, you try 1 - 15 and thats 16 tries. if it doesn't break, then try floor 31 and if it breaks, then try 17 - 30 (so 16 tries, including the try on floor 16). And on and on (45, 58, 70, 81, 91, 100). If you reach 91, you'll have tried 7 floors so far and if it doesn't break, then there's 9 more tries to get to 100 (thus 16 in the worst case)

Go to the 100th floor and drop the first bulb. It WILL break. Done, 1 drop. It doesnt say whats the lowest floor it will break at, just at what floor will it break with least drops. Thus floor 100.

>>you drop it from floor 12 next... if you broke it on 50 and 25... you are out of luck and out of bulbs...

If you do a binary search, what happens if it breaks at floors 50 and 25?

Let F(s, n) be the optimal worst-case number drops for s stories and n bulbs. Suppose we drop at floor f, constituting one drop. If it breaks, we must make up to F(f-1, n-1) drops. If it doesn't break, we must make up to F(s-f, n) drops. Thus, for a given floor f, we have up to 1 + max { F(f-1, n-1), F(s-f, n) } drops. Optimizing over f: F(s, n) = 1 + min{ max { F(f-1, n-1), F(s-f, n) } for f in 1..s} Using the appropriate base cases, we have F(100, 2) = 14, as mer has given. Another way to think about it is in terms of decision trees. We want to construct a binary decision tree with leaf nodes for floors 1..100, and at most one "left" turn per path from root to leaf. To minimize the height of the tree, we want to reduce the variance in the length of each root-to-leaf path. This suggest we try dropping the first bulb at floors of the form: a, a-1, a-2, .. a-b, where the sum a + (a-1) + .. + (a-b) is equal to or barely over 100, so that determining almost any floor (possibly excluding the top few) takes a drops. Using this approach, we get the sequence of drops that mer has suggested.

Start moving up in increments of 10 floors and dropping the bulb until it breaks (ie: drop from floor 10, if it doesn't break, drop from floor 20, etc.). Once the bulb breaks, move down to the floor above the last floor it broke on and start moving up floors in increments of one until the second bulb breaks. This results in a worst case scenario of 19 drops.

0 drops, 1 bulb......stop thinking like computer nerds. Use physics or an engineering mindset. They didn't prohibit the use of any tools. Grab a scale, figure out force req'd to fracture bulb. Calculate acceleration due to gravity adjusting for air resistance/barometric pressure at location (trivial for anyone who took a 1yr physics course). Figure out how many meters up you need to be based on the req'd acceleration. Done....

In theory, use one bulb to determine an interval, and use the second bulb for a linear search within the interval. The solution that decreases the interval by one for each trial is quite clever. In practice, however, take the nature of the problem into account: Start on the first floor and move up by one floor. That's the answer I would be looking for.

Drop from 1st floor. If it didn't break, drop the same bulb from 2nd. If it still didn't break, drop the same bulb from 3rd... repeat as necessary. Only one light bulb required :)

In my experience light bulbs break when dropped from any height above 3 feet

It's a light bulb. It will break when dropped from the 2nd floor. Drop it there then go to the first floor, hold it over your head and drop it.

14

Well done @mer I have seen this question posed many ways, and that is the best answer I have ever seen. Sure hope I get asked this one now

Even a drop from the ceiling of 1st floor, a simple light bulb will break. thats what i think

Assuming you know nothing about the light bulb, I believe the 14, 27, 39, 50, 60, 69, 77, 84, 90, 95, 99 increment would by far be the best option. I compared it against fixed I did the calculations below with this method, fixed increments of 10 and fixed increments of 9. Average Drops per Digit (1-100) - 14inc is 9.47 -10fixed is 10 - 9fixed is 10.02 Max Potential Drops - 14inc is 14 - 10fixed is 19 - 9fixed is 19 Comparing the 3 vs the digits, how many times are they the most efficient method - 14inc wins out 48 times - 10fixed wins 41 times - 9fixed wins 40 times *Note the total is over 100, if there was a tie those methods each got a win. The only concern against the 14 increments is that it performs poorer at the beginning, but if you don't know when exactly it will break and believe that it could be at any floor then it wouldn't matter.

We can quickly calculate both which floor to test first and the worst case number of drops (they are the same number) for any building with N stories, by calculating the integer value of the square root of 2N. For a building with a 100 stories sqrt((2 x 100) = 14.1429… which we truncate to 14. So we first drop one bulb at the 14th floor. If the bulb survives, we proceed to floor 14+13, and as long as the bulb does not break - floors 14+13+12, 14+13+12+11 and so on. Once the bulb breaks we go back to the floor one higher than than the prior floor tested (or 1 if it breaks from floor 14).

If we employ a brute force approach we can find the floor with N-1 drops in all the cases. Which isn't very efficient so let's move on to a binary search approach. In a binary search, we drop from the 1st and 51 floors. If the bulb breaks in either of these two cases, we are only left with one bulb and we've only reduced the floors by 50. So, In the worst case we still might need to drop N-1 times to find the floor after finding which half the bulb breaks in. The next approach is called Divide a bit conquer a little, which is a mixture of the above two methods. Essentially we drop the bulbs in every 10th floor and in the floor in which the bulb breaks, we do N-1 drops to find the exact floor. In the worst case, this approach takes 19 drops to find the exact floor, if the floor is 99. It's efficient but we can do better. The final and last approach, would be to reduce the floor count on each drop such that we reduce it linearly on each drop. For example, if we plan to drop the egg within x floors, in the next drop we drop the egg from x-1 floors. x is a constant number of floors. So with this logic we can see that we reduce the floors linearly with each drops which can be represented as : x + (x-1) + (x-2) + (x-3) + ......... + 1 = 100 This can be further reduced to Sum of N natural number such that it reduces to : x (x +1)/2 = 100 So, in this case x will be equal to 13.7 which can be approximated to 14. So in the worst case, it would require us a maximum of 14 drops to find the exact floor.

To find the floor at which the bulbs will break using the least number of drops, you can use a binary search algorithm. Here's how it would work: Start by dropping one of the light bulbs from the 50th floor. If the bulb breaks, then you know that the floor at which the bulbs will break is somewhere in the first 50 floors. If the bulb does not break, then you know that the floor at which the bulbs will break is somewhere in the 51st to 100th floors. Next, drop the other light bulb from the 75th floor (the midpoint between the 51st and 100th floors). If the second bulb breaks, then you know that the floor at which the bulbs will break is somewhere in the 51st to 74th floors. If the second bulb does not break, then you know that the floor at which the bulbs will break is somewhere in the 75th to 100th floors. Repeat this process, using the midpoint of the remaining range as the floor from which to drop the next bulb, until you have narrowed down the range to a single floor. Using this binary search approach, you should be able to find the floor at which the bulbs will break using a maximum of 14 drops (since log2(100) = 6.64, which is slightly less than 7).

n*(n+1)/2 = 100. n approx = 14. In worst case u can figure it out in 14 drops. 14th, 27th, 39th, 50th, 60th, 69th, 78th, 85th, 91st, 96th, and (optionally) 100th until it breaks.

Easy. Answer is zero. You don't need a test to find out that a lightbulb is going to break, even when you drop it from the first floor, because it's made of glass.

BigO(100/X + X-1), Where X is the number of floors. 100/X calculates the dropping times to break the first one and X-1 is the additional maximum overhead to break the second one starting from the previous dropping floor to the floor the previous bulb was broken. If you solve the derivative of the above equation equal to zero, the optimal solution becomes 9.9 ~= 10 . Worst case = 100/10 + 10 -1 = 19

If its a glass bulb it will break from a 2ft height...i wont even care climbing any floors to check.

Once you break the first light bulb, you are FORCED to start at the highest safe floor + 1 (i.e. highest floor that you safely dropped bulb #1 from) and drop bulb #2 one floor at a time, moving upward. Therefore, the algorithm for the first light bulb is critical (cuz once it breaks you are counting by 1's upward). Binary search starts at the 50th floor ==> max # drops = 50 Choosing fixed increments rather than binary search, e.g. start at 10, increment by 10, yields better results ==> 25 The ideal solution is 14 drops ==> Start at 14, increment by 14 each step until it breaks (leaving for the reader why 14 is optimal).

It doesn't matter what floor you are on to make a bulb break. Doesn't it matter how high off the floor the bulb is dropped. If I am on the 5th floor and the bulb is sitting on the floor of the 5th floor, how high off of that 5th floor do I need to drop it before it breaks. This is a misleading question. The question doesn't say that you will drop the bulb out the window.

Drop both from eye level. Both will break, and I answered the question without even climbing one stair. Efficiency isn't always about math..Common sense

Depends on how accurate u want to be. If i want exact answer, drop one from fifty, if it breaks start from first floor woth the remaining bulb. If it does not break, then start from fifty first florr. u will iterate fifty times as worst case. If u want a approximate answer, u can do binary way with give or take twenty five floors. Step over based on accuracy needed.

You are all ignoring valuable information in this question. We are talking lightbulb, not bowling ball, and building, not step ladder. The bulb will almost certainly break by being dropped from the second floor (assuming US numbering conventions). The chance of it surviving a 3rd floor drop are miniscule, but not zero. The chance of a 4th floor drop, even less. Therefore, drop it from the 3rd floor first. If it breaks, go to the second floor and try. If that breaks you know the answer is 2. If it by some miracle doesn't break from the 3rd floor drop, the answer is 4, but take the elevator up one floor and drop it just to see. Rinse and repeat to 5, but since it will have already broken, go out and grab a beer, and tell your friends how much fun you just had.

Answer: 14 drops Mathematically: 14 is the first number n, where the sum of numbers from 1 to n is greater than 100 Trial and error: The worst case happens when the bulbs break at floor 13. If you start from the 14th floor and the bulb breaks, then you start at the bottom floor and work your way up. If it doesn’t break and you try it again from the 28th floor and it breaks, then you go back down to the 15th and work your way up 1 floor at a time.

Alright guys...you have two light bulbs. ...the second one has to be used for linear search, let the worst case number of items to be searched be x, then your interval will also have to be x, which will result a worst case of 100/x drops for the first light bulb. So now you are just trying to minimize n=100/x+x, find n'=0 when x=19...the candidate's answer is correct.

I meant...x=10. and n=19.

@Rich: I am sure they were hoping for you to give them a computing answer since they don't do physics, and rather do computer science. mer's answer is correct: 14.

Yes, but doing each floor, that will give you the most drops -- question relates to optimizing for "least" number of drops -- I didn't think about being able to re-use the bulbs...that obviously is helpful. Maybe a fibonaci sequence once you determine a "break" floor and a "non-break" floor. I'd probably fail completely at coding it...knowledge of optimization and prediction theory would certainly be useful.

Let f(m,k) be number of tries for m lamps and k floors. Obviously f(1,k)=k. let f(2,k) be s. k<=(s-1)+(s-2)...(1) =s(s-1)/2. Therefore f(2,100)=15.

Start with bulb 1 and drop it from floor 2. Doesnt break? then floor 4 Doesnt break? keep dropping the same bulb moving even number of floors all the way upto floor 100. If on some even floor the bulb breaks drop the second bulb from the odd floor below the even floor, to detect if its the even or the odd floor that breaks the bulb Best case detection: 2 tries (first bulb breaks on 2nd floor, second bulb breaks on 1st floor) Worst case: 51 tries (the fist bulb breaks at 100 and second bulb breaks or does not break at 99th floor.. )

first do a binary search (agressive first step - fast) with 1 bulb. when first breaks, you know X(last but one fall - success) and Y(last fall - failure). now do a linear search starting from X(conservative but accurate second step - slow). complexity = in between logN and N.

Use Binary search starting with the middle 50 The complexity of binary search is logN . So it will be log(100) < 7. Based on my experience, I think it will be floor 1 itself .

Surely a binary search method would be more efficient i.e. starting at 50 and either going up or down 25 floors based on if it breaks or not.