Originally posted by spashta-wakta
* A good puzzle:
You have two glass balls. They break when dropped from floor x & above but not when dropped from floors 1 to x-1. Given a 100-storeyed building, what is the minimum number of throws in which you can determine the exact floor x?
(It is obvious that you must ensure at least one ball stays unbroken till you determine x!)
Nice garden SW 😊 Madanbaan is very rare type of flower I believe.. Had heard of it but had not seen before.
Puzzle solution:
I think we need to tackle the problem in BST (binary search tree) way if we want to do better than linear time..
So if we apply binary tree algo as is, we need to start with floor no. F = 50 and then slowly work out our way depending on two possibilities -
1. the ball breaks on 50th floor OR
2. it does not break on 50th floor.
So in case 1, the floor x lies between 1-49 and in case 2 the floor lies between 51-100. In case 2,we can repeat the process of selecting the median floor (floor no. 75) and continue. In case 1, the worst-case tries will be 1 to 49.
In any case, we have halved our number of tries, which is tremendous gain over the brute force solution of x-1 tries.
Now, we can choose a better value of floor F (the floor on which we'll try out first throw) and reduce our tries. So let's say we decide on F = 5, we'll first throw one ball from 5th floor. If it doesn't break, we'll go to floor 2F (i.e. 10th) and repeat the same. If it breaks on 5th, we can try all floors from 1 to 4.
It will need a bit of math to find the optimal value of F. I'll do it later and try to find the best value of F, if possible 😊
