I recently came across an interview question from Apple via entrepreneur.com. The question reads like this:
If you have two eggs, and you want to figure out the highest floor from which you can drop the egg without breaking it, how would you do it?
The given answer is sequentially going upwards, dropping one of the eggs on every floor and figuring out if it is still sound. This trial and error approach however is \(O(n)\) and far from optimal.
Let's say, we have a house with \(n=100\) floors. For a minimal number, we start at floor 14. If the egg breaks here already, I go to floor 1 and continue sequentially up to floor 13 with the second egg.
If the egg didn't break, I go 13 floors upwards and arrive on floor 27. If it breaks here, I have to test floors 15-26 with my second egg and again have 14 trials.
Again, if the egg did not break on floor 27, I continue and go 12 upwards. Following this algorithm, you'll come up with the following jump pattern:
\[14 \rightarrow 27 \rightarrow 39 \rightarrow 50 \rightarrow 60 \rightarrow 69 \rightarrow 77 \rightarrow 84 \rightarrow 90 \rightarrow 95 \rightarrow 99\]
If the egg breaks on floor 99, I have to test 96, 97 and 98. After 11 trials up to 99 and 3 more tests, 14 again.
If the egg doesn't break on floor 99, I can conclude that it must break on 100. I therefore always need 14 trials.
This algorithm is optimal. If there were an algorithm which would need 13 trials, I would come to floor 91 only when following the algorithm from above. If the egg did not break until floor 91, I would need more trials but the 13 trials are exhausted already and we get a contradiction.
We used \(n=100\) above, but let's generalize the algorithm. For \(n=2\), the output should be \(0\), since \(2\) can't be the edge floor, so the edge floor is the first one and there's no need to throw any eggs. For \(n=3\), the output should be 1. The edge floor is either the first or the second. If you throw a egg from the second floor it either breaks, which means that the first floor is edge, or it doesn't, which means that the second floor is the edge floor. That means that
\[\begin{array}{rl} f(0) &= 2\\ f(x) &= f(x-1) + x\\ & = 2+\sum\limits_{k=1}^xk \\ & = 2 + \frac{x\cdot(x+1)}{2} \end{array} \]
If we have a house with \(n\) floors, we're looking for \(x\):
\[\begin{array}{rrl} & f(x) &\geq n\\ \Leftrightarrow & 2 + \frac{x\cdot(x+1)}{2} &\geq n\\ \Leftrightarrow & x^2+x &\geq 2n-4\\ \Leftrightarrow & (x+\frac{1}{2})^2 &\geq 2n-4+\frac{1}{4}\\ \Leftrightarrow & x &\geq \sqrt{2n-\frac{15}{4}}-\frac{1}{2} (\text{as }x\geq0) \end{array}\]
Therefore, the minimal number of trials is given by: \[x=\left \lceil\sqrt{2n-\frac{15}{4}}-\frac{1}{2} \right \rceil = \left \lceil\frac{\sqrt{8n-15}-1}{2}\right \rceil\]
For the lazy folks, try this calculator:
Floors: