An egg breaks only if dropped from above a threshold floor, within this 100 story building. Every time you drop the egg, it is counted an attempt. You are given three eggs, find an algorithm to deduce the threshold floor, with minimum number of attempts in worst case!
Answers
Answer:
Step-by-step explanation:Let us make our first attempt on x'th floor.
If it breaks, we try remaining (x-1) floors one by one.
So in worst case, we make x trials.
If it doesn’t break, we jump (x-1) floors (Because we have
already made one attempt and we don't want to go beyond
x attempts. Therefore (x-1) attempts are available),
Next floor we try is floor x + (x-1)
Similarly, if this drop does not break, next need to jump
up to floor x + (x-1) + (x-2), then x + (x-1) + (x-2) + (x-3)
and so on.
Since the last floor to be tired is 100'th floor, sum of
series should be 100 for optimal value of x.
x + (x-1) + (x-2) + (x-3) + .... + 1 = 100
x(x+1)/2 = 100
x = 13.651
Therefore, we start trying from 14'th floor. If Egg breaks
we one by one try remaining 13 floors. If egg doesn't break
we go to 27th floor.
If egg breaks on 27'th floor, we try floors form 15 to 26.
If egg doesn't break on 27'th floor, we go to 39'th floor.
An so on...