5
$\begingroup$

Question: You are given access to a multistory building. You have N eggs and are allowed D maximum drops from their window.

Rules: If a egg is dropped from window of floor F and it breaks, it will break for all floors > F.

If an egg is dropped from window of floor F and survives, it will survive for all floors < F.

What is the maximum number of floors you can check in the worst-case?

E.g: With 1 egg and 5 drops, you can check at most 5 floors (1, 2, 3, 4, 5)

With 2 eggs and 5 drops, you can check at most 9 floors (2, 4, 6 ,8, 9)

EDIT: By "maximum floors you can check", I mean the highest floor for which you can guarantee that you know the outcome for all floors <= to it. For. e.g in N = 1, D = 5 case, there is no algorithm that guarantees you will know the outcome at every floor <= 6 in the worst case. This is because in the worst-case: drops from 6, 5, 4, 3, 2 break and you don't know what will happen at floor 1 since you have no more drops left.

My solution is as follows

findMaxFloors(N,D)
{
 nextFloor = 0

 while (D > 0)
 {
    nextFloor += MIN(N, D);
    D = D-1;
 }

 return nextFloor;
}

But the solution given on the forum is more complicated (using recursion) maxFloors(N+1,D) = maxFloors(N, D-1) + 1 + maxFloors(N+1, D-1)

I would appreciate any suggestions on the conditions under which my solution won't work.

$\endgroup$
  • 1
    $\begingroup$ I don't understand what you mean by "maximum number of floors you can check"? What number are you trying to compute? (Also, could you edit the question so you're not using $N$ to mean both the number of eggs available and the floor from which an egg is dropped?) $\endgroup$ – David Richerby Oct 1 '16 at 12:13
  • $\begingroup$ Explain us the riddle as if we didn't already know it. $\endgroup$ – Yuval Filmus Oct 1 '16 at 14:25
  • $\begingroup$ @DavidRicherby, I did the edit. Thanks. By "maximum floors you can check", I mean the highest floor for which you can guarantee that you know the outcome for all floors <= to it. For. e.g in N = 1, D = 5 case, there is no algorithm that guarantees you will know the outcome at every floor <= 6 in the worst case. This is because in the worst-case: drops from 6, 5, 4, 3, 2 break and you don't know what will happen at floor 1 since you have no more drops left. $\endgroup$ – Smart Home Oct 1 '16 at 16:04
5
$\begingroup$

First we'll clarify the problem a bit. We have $n$ eggs, which we can drop from any floor we want. We also have the constraint that we are allowed a total of $d$ drops of these eggs (rather than $d$ drops per egg). Obviously, when we drop an egg and it breaks, we can't drop it again. Let $f(n,d)$ be the maximum number $M$ such that with $n$ eggs and $d$ drops, we can completely describe the behavior of our experiment for floors $1,\dotsc,M$.

In other words, with $M=5$ the possible outcomes are [YYYYY] (the eggs break when dropped from all 5 floors), [NYYYY] (the egg survives a drop from floor 1 but no higher floor), and [NNYYY], [NNNYY], [NNNNy], and [NNNNN]. Obviously, in all possible descriptions, all the N's must come before all the possible Y's

With that out of the way, let's tackle the recursion $$ f(n,d)=f(n-1,d-1)+1+f(n,d-1) $$ Our plan of attack is to drop the first egg from floor $x$, yet to be determined. That egg either breaks or doesn't:

  1. If it breaks, we know it will break when dropped from any higher floor as well, so we're left with $n-1$ eggs and $d-1$ more drops. In other words, we're looking at the lower floors and there will be $f(n-1,d-1)$ of them, namely floors $1, 2,\dotsc, f(n-1,d-1)$.
  2. Since we've already settled the behavior at floor $x$, we need to have $x=f(n-1,d-1)+1$.
  3. If it doesn't break, we know it won't break when dropped from a lower floor, so we still have $n$ eggs and $d-1$ drops remaining, which will mean that we can determine the behavior of the higher $f(n,d-1)$ floors. They will start at floor $x+1$ and will cover floors $x+1, \dotsc, x+f(n,d-1)=f(n-1,d-1)+1+f(n,d-1)$, exactly as the recursion stated.

For example, you correctly observed that $f(1,5)=5$ but your value for $f(2,5)$ was low. In fact, $f(2, d)=d(d+1)/2$, which is 15 in the case where $d=5$. Start with the first drop from floor 5, and you'll see that you can indeed determine the egg behavior at all of the first 15 floors.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.