Suppose that there is a building with 100 floors. You are given 2 identical eggs. The most interesting property of the eggs is that every egg has it’s own “threshold” floor. Let’s call that floor N. What this means is that the egg will not break when dropped from any floor below floor N, but the egg will definitely break from any floor above floor N, including floor N itself.
What strategy should be taken in order to minimize the number of egg drops used to find floor N (the threshold floor) for the egg? Also, what is the minimum number of drops for the worst case using this strategy?
a linear search is indeed necessary with the 2nd egg because we can not risk breaking the 2nd egg before we even find the answer.
reduce the worst case scenario by trying to make all possible scenarios take the same number of drops.
x + (x-1) + (x-2) + (x-3) + ... + 1
x(x+1)/2 = 100
When the sum of the series above equals 100, we get x = 13.651, which rounds up to 14. This means that we should start from floor 14 (which is our x) and then move up x-1 (13) floors to floor 27 if the egg doesn’t break and then move up x-2 (12) floors to floor 39 and so on if the egg still does not break.
This is the number of drops required as we move up the floors in the building:
Drop Floor
#1 14
#2 27
#3 39
#4 50
#5 60
#6 69
#7 77
#8 84
#9 90
#10 95
#11 99
#12 100
Read full article from 2 Eggs 100 Floors
What strategy should be taken in order to minimize the number of egg drops used to find floor N (the threshold floor) for the egg? Also, what is the minimum number of drops for the worst case using this strategy?
a linear search is indeed necessary with the 2nd egg because we can not risk breaking the 2nd egg before we even find the answer.
reduce the worst case scenario by trying to make all possible scenarios take the same number of drops.
x + (x-1) + (x-2) + (x-3) + ... + 1
x(x+1)/2 = 100
When the sum of the series above equals 100, we get x = 13.651, which rounds up to 14. This means that we should start from floor 14 (which is our x) and then move up x-1 (13) floors to floor 27 if the egg doesn’t break and then move up x-2 (12) floors to floor 39 and so on if the egg still does not break.
This is the number of drops required as we move up the floors in the building:
Drop Floor
#1 14
#2 27
#3 39
#4 50
#5 60
#6 69
#7 77
#8 84
#9 90
#10 95
#11 99
#12 100
Read full article from 2 Eggs 100 Floors
