Fog Creek Software
Discussion Board

dropping orbs (answer)

I found another explanation of the solution elsewhere on the web which I think is easier to understand.

(from:  )

"Ideally we would like a binary search-like algorithm to determine the floor. However, the complication is that if we try a floor too high, then our egg breaks and we are stuck. So we must make sure our guess is always below the actual answer.

The advantage of having 2 eggs is that we are now allowed to guess higher than the actual floor one time and still be ok. Suppose our upper bound is k [Note: k is the maximum number of drops you will make, for both the 1st and 2nd eggs]. For our first drop we could try a floor as high as floor k. If the egg doesn’t break, we keep moving up. However, if the egg breaks we can try all the floors below floor k and still determine the floor within k drops. After dropping an egg on floor k,we have k-1 remaining drops, and so the same logic applies. We can now move up to floor k +(k-1) [Note: we goto k + (k-1) because we have already used one drop and must have k-2 spare to determine the exact floor, if it breaks at k + (k-1)]. So eventually we move up as high as

Summation(1<=i<=k)i = k(k+1)/2 [Note: This is derived from the pattern k + (k-1) + (k-2) + ... + 2 + 1 = k*(k+1)/2]

The smallest value of k such that this value will be >= 99 is 14."

[Note: comments in square brackets are my additions.]

Siddhant Bhansali
Monday, October 6, 2003

*  Recent Topics

*  Fog Creek Home