You have an building with N floors and 2 identical glass balls. You can drop a ball from any floor. Determine minimum floor from which either of the balls will break in the least number of drop attempts.
Start at the top floor (lets say t). Then go to t-2^n in the nth try till the first ball breaks at say t-2^k. From that point go serially downwards from t-2^(k-1).
Hmmm.. Try playing it as a game. Say ur first attempt broke the ball then u have to go 1,2,3... to find the min floor from which it breaks. So worst case here is N. Can do better.
An optimization to Srinath's approach - rather than having length of each internal that first ball creates as constant, need to come up with a function such that the intervals reduce as we go up so that the sum of drops of first and second balls is equal in all possibilities. Will need to do some math to get the value of x, the initial number of steps such that ..
I'm quite sure this is right. Start with the lowest floor, and increase exponentially till the ball breaks, i.e., after 1st floor, then 2nd, then 4th, then 8th, then 16th, and so on. The moment the ball breaks, use the second ball incrementally, from the last check point till it breaks.
So, if the kth floor was the answer, you would find it in
ceil(log(k)) + k/2 steps
(The second incremental phase is required since you have only one ball and can't take a chance. The first exponential phase is the quickest to get to the right region).
6 comments:
Is this correct?
Start at the top floor (lets say t). Then go to t-2^n in the nth try till the first ball breaks at say t-2^k. From that point go serially downwards from t-2^(k-1).
Hmmm.. Try playing it as a game. Say ur first attempt broke the ball then u have to go 1,2,3... to find the min floor from which it breaks. So worst case here is N. Can do better.
Immediate intuition says, start with 1, and increment by squareRoot(N). And then, in that particular block of root(N) go one by one.
This would have something like 2*root(N) as worst case.
But, remember reading a more complex solution that would reduce the worst case further. Let me not post the details here and spoil the fun.
An optimization to Srinath's approach - rather than having length of each internal that first ball creates as constant, need to come up with a function such that the intervals reduce as we go up so that the sum of drops of first and second balls is equal in all possibilities. Will need to do some math to get the value of x, the initial number of steps such that ..
x + (x-1) + (x-2) + ... (x+1)/2 = N
I'm quite sure this is right. Start with the lowest floor, and increase exponentially till the ball breaks, i.e., after 1st floor, then 2nd, then 4th, then 8th, then 16th, and so on. The moment the ball breaks, use the second ball incrementally, from the last check point till it breaks.
So, if the kth floor was the answer, you would find it in
ceil(log(k)) + k/2 steps
(The second incremental phase is required since you have only one ball and can't take a chance. The first exponential phase is the quickest to get to the right region).
-- Uday
As there are two balls so first ball should be used to narrow down the search. And second ball should be use to find the actual floor.
rest after dinner
Post a Comment