Last year, I posted this algorithm question, and said I would give the solution shortly after. I was looking over stuff I had posted on my blog today, and realized I never posted a solution, so here it is:

Note: To avoid and confusion, “story” and “floor” mean the same thing in this example.

The Problem:

A firm wants to determine the highest floor on its n-story building from which a device can fall with no impact on the device’s functionality. The firm has two identical gadgets that you can experiment with (each costs $1,000,000). You are allowed to break both gadgets,  but no extra gadgets will be provided. Design a brute force algorithm in the best efficiency class to solve this problem.

The most simple solution seems pretty obvious. You start at the first floor and drop the gadget. If it breaks, you know it cannot be dropped from anything higher than 1 story. If it doesn’t you go to the next story and drop it. You keep doing this until the item breaks. When it breaks, you know that the last possible story that you can drop it from without breaking is the previous story.

There must be a much faster way, right?  What if you had a building with 2000 floors, and the gadget would not break until floor 1900? You would waste a lot of time using this simple brute force method. The asymptotic time complexity of this algorithm is linear, or . So assuming it takes on average 10 minutes to drop the gadget, take the elevator all the way down to the first floor, inspect the gadget to see if it is broken, and take it all the way back up to the next floor, it would take you 1900*10 minutes to find the answer to your problem. That is A LOT of time.

Another possible solution, which is much more elegant: (note: this is still considered a brute force algorithm)

Remember, we have two gadgets to use during this testing project.

First, you drop the gadget at where n is the number of stories. If the gadget breaks at this story, you know the lowest possible story it will not break is between story 1, and story . If it doesn’t break at then drop the gadget at .

If it breaks, then you know the lowest possible story it will not break is between and . If it doesn’t break at , then you just increase the multiple by 1. You keep doing this until you find a story where it breaks.

For instance, lets assume it would break at . You start at floor (remember, we already dropped it at so we don’t need to check it again). If it breaks, you know the lowest story is .

If it doesn’t you just keep incrementing until you get to . If it does not break at this floor, you know the lowest possible floor is that floor, since we know it broke at (we already tested it an it broke at that floor).

This solution has am asymptotic time complexity of or

jonnale Computer Science