Simple Answer.
The simplest way to obtain the minimal floor is to throw an egg from the first floor, then from the second and so on. This way when the egg is finally broken then we will know that this is the floor. This is a reliable algorithm, but in the worst-case scenario it would take 100 throws.
The important thing to notice is that it is the only reliable algorithm when you have only one egg. So you need to start using this algorithm when you break the first egg.
Step-by-step explanation: Intuitive answer.
This way, our first egg should be used to split the 100 floors range into smaller ranges as efficiently as possible. Thus, an intuitive and popular answer is to throw the first egg from 1/n-th of the floors to check. For instance 1/3. Then the algorithm will look like the following:
Throw the egg from 33rd floor. If it breaks, then we check the first 32 floors using the second egg.
Otherwise, we throw the egg from 33 + (67 * 1/3) = 55th floor. If it breaks, then we check floors 34 to 55 using the second egg.
β¦
Worst case scenario for 1/3 is max(33, 24, β¦) = 33. This way we might find a perfect n that optimizes the number of throws using some dynamic programming. This is a valuable solution that presents programming thinking, but it is not an optimal solution.
The optimal solution is when all arguments of this max function are equal. How do we achieve it? Looking from the end, the last D(n) is going to be 1, because we will finally get to the point where there is only the single floor for the first egg. Therefore D(n-1) should be equal to 2 because it has one less throw of the first egg.
We see then that the first egg should be thrown finally from the 99th floor, previously from 99β2=97, previously from 97β3=94, 90, 85, 79, 72, 64, 55, 45, 34, 22 and the 9th floor. This is an optimal solution! This way, we need 14 throws in the worst case scenario (the smallest difference is 13, but we had to make one extra throw on the 9th floor).
Simple equation to find the answer is following:
Where f is number of floors. This can be simplified to: min n*n+ divided by 2 greater than f
That is equal to: n=ceil 8f + 1 - 1, divided by 2
