The approach is the same irrespective of the critical floor (out of
necessity as we don’t know what it is!). Anyway, for the scenario of 100
floors and 2 eggs the first drop is from floor 14. If the egg breaks then
we know the critical floor is below but we only have a single egg left so
we have no choice but to test from floor 1 and work our way up. In the
worst case of the critical floor being 13 then we would have performed 14
total drops before this is established. If the egg had survived the first
drop then we still have 2 eggs left so we take our next drop at floor 27
(i.e. 13 floors further up) - if it smashes we use the final egg to test
the 12 floors between 15 and 26 (so again, upto 14 drops total). If the egg
survived the second drop at floor 27 we reuse this egg and drop from
floor 39 (i.e 12 floors further up). We carry on in this manner reducing
the floor increment by one each time to account for the fact that we have
one less drop available.
If in our example, the critical floor was 100 and thus our eggs kept
surviving the falls then the sequence of drops would be at floors:
But, you might say “that’s only 12 drops and your algorithm says the
minimum number of egg drops is 14!”. So what’s going on here?
Well actually, in my opinion, the title of minimum egg dropper is slightly
misleading. What we are actually trying to find out is the maximum number
of egg drops that would be required if you used the optimum testing method.
If you think about it, the minimum egg drops required for any problem is
just two - but this would require that the dropper is lucky enough to take
the 2 drops - on and immediately below the critical floor. I guess another
way to think of it is - the minimum number drops that is guaranteed to
reveal the critical floor (provided you follow the prescribed method).
So returning to our problem with 100 floors and 2 eggs. We have shown that
we can definitely find the critical floor if we take 14 drops. Now we need
to show that 13 drops is not sufficient. Using the same method as before
and if again we say that the critical floor is 100 then our drops would be
on the following floors:
Ah! So here we have taken 13 drops but we have only narrowed down the
possibilities to within 9 floors (92 to 100). Therefore the 14 drop method
is the minimum that is guaranteed to find the critical floor.
Just briefly returning to you example of the critical floor at 57 the
testing sequence would be
14,27,39,50,60s,51,52,53,54,55,56,57s = 12 drops (the ‘s’ suffix denotes a
So this only required 12 drops. However, this does not mean the answer is
12 because this method might require 14 drops if the critical floor was
elsewhere (floor 59 for example).
Hope that helps…