2 Eggs and 100 Floors
Let’s talk about the 2 Egg problem, courtesy of Interview Cake.
The Problem
A building has 100 floors. One of the floors is the highest floor an egg can be dropped from without breaking.
If an egg is dropped from above that floor, it will break. If it is dropped from that floor or below, it will be completely undamaged and you can drop the egg again.
Given two eggs, find the highest floor an egg can be dropped from without breaking, with as few drops as possible.
Assumptions & Egg(de) Cases
We can assume the eggs break at the same floor and what we’re looking for is the next floor down — our highest-non-breaking-floor (n). We can also assume once an egg is broken, it’s gone forever.
Some solutions are pretty simple: if we don’t care about how many tries it takes, you can just start dropping eggs on floor 1 and go up until you’ve reached the correct floor. Floor by floor would get it done, but in our worst case scenario (the egg breaks at floor 100) this means that linearly, our worst case is 100 drops to find our n floor.
My first thought, following a week of studying data structures and search algorithms, is to divide and conquer with a simple binary search. But we can immediately rule out binary search because we only have the 2 eggs.
With a binary search strategy, we’d start with floor 50, and drop the egg from the 50th floor. If the egg breaks we know our n is below 50, if it’s intact the floor we want is above 50. Supposing the egg breaks, the problem here is now we’ve lost an egg and only narrowed down our search by 50 numbers. The next step would normally be to split that 50 again and dropping the egg at floor 25, but if it breaks we still haven’t found our floor. If it doesn’t, it we’ve only delayed the inevitable by one more step — and still no solution. Worst case scenario: we have to drop our eggs 50 times.
Divide a Little, Conquer a Bit
The next solution takes a little bit of the linear approach and mixes in a little of the splitting from our binary approach. We can start off by dropping an egg at floor 10, increasing the drop floor by 10 at a time, then going back to drop one floor at a time until we find that n. If our egg breaks at floor 10, we know n is one of the 9 floors below us.
Worst case, the egg drops and doesn’t break until floor 100 (10 drops) and we drop the second egg but don’t break it for floors 91–99.
It brings our worst case drop count to 19 drops.
Seems relatively straightforwards, but we can still improve our number of drops.
13.651 Drops
The next approach can reduce our worse case scenario by balancing the linear drops and our 10 floor drop increment. If getting to the higher floors means more drops overall, we need to decrease the drops we need to perform linearly. We’re essentially trying to make all possible scenarios take the same number of drops to solve.
If we drop our first egg from floor x (10 in our 10 floor strategy), the linear portion of our strategy is x-1 (9 in the above strategy). Our drop count is:
x + (x - 1)If the egg doesn’t break on the first drop our drop count increases by one, so we’ll need to remove a drop from our floor by floor drop count — the next drop should be from x-1 floors up. Every additional floor jump will need to have one less floor, so that when we get to the linear portion of the solution we’ll have one less floor to check. We continue removing one floor until we only have 1 floor to check:
x + (x-1) + (x-2) + (x-3) + ... + 1Which simplifies to:x(x + 1)/2
Because there are 100 floors in our problem, we solve for x when the entire summation is equal to 100:
x(x + 1)/2 = 100And some math...x = 13.651
This means we want to start dropping from floor 14, jump up 13 floors to drop from floor 27, jump up 12 floors to drop from floor 39, and so on. Our worst case scenario is then a drop count total of 14.
