* You are given 2 eggs.
* You have access to a 100-storey building.
* Eggs can be very hard or very fragile means it may break if dropped from the first floor or may not even break if dropped from 100 th floor.Both eggs are identical.
* You need to figure out the highest floor of a 100-storey building an egg can be dropped without breaking.
* Now the question is how many drops you need to make. You are allowed to break 2 eggs in the process
ANS:
The maximum drops is 14.
take it as n(n+1)/2 is just greater than or equal to 100.so n=14.
Algo:
i=14,j=13
1.drop the egg from ith floor
if egg breaks then
drop egg from (i-j)th floor and then go one floor up and keep droping(until req floor is found)
else
i=i+j
j--
if(j>=1)
goto step 1.
EXPLANATION:
Lets take the case with 16 as the answer
1 + 15 16 if breaks at 16 checks from 1 to 15 in 15 drops
1 + 14 31 if breaks at 31 checks from 17 to 30 in 14 drops
1 + 13 45 .....
1 + 12 58
1 + 11 70
1 + 10 81
1 + 9 91
1 + 8 100 We can easily do in the end as we have enough drops to accomplish the task
Now finding out the optimal one we can see that we could have done it in either 15 or 14 drops only but how can we find the optimal one. From the above table we can see that the optimal one will be needing 0 linear trials in the last step.
So we could write it as
(1+p) + (1+(p-1))+ (1+(p-2)) + .........+ (1+0) >= 100.
Let 1+p=q which is the answer we are looking for
q (q+1)/2 >=100
Solving for 100 you get q=14.
So the answer is: 14
Drop first orb from floors 14, 27, 39, 50, 60, 69, 77, 84, 90, 95, 99, 100... (i.e. move up 14 then 13, then 12 floors, etc) until it breaks (or doesn't at 100).
