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.
Answers
Answered by
3
First thought which comes to our mind is to use binary search, we first drop Egg#1 from 50th floor, if it does not break, then try the middle of second half, if breaks then we have to try each floor in first half. But this will give worst case number of drops as 50(if it brakes on 50th floor, then we have to try from 1 to 49 floors sequentially).
Second thought is to try xth floor then 2xth floor till 100th, in this case worst case time will be (100/x)+(x-1). worst case will be when Egg #1 breaks at 100th floor then we have to try Egg #2 from (100-x)th to 99th floors. In (100/x) + (x-1) equation, with increase in x, 100/x decreases while (x-1) increases, thus we can minimize it when 100/x = (x-1), this gives x ~10, which gives worst case number as 19 drops.
But increasing the floor every time by x is not a very nice idea, as with each new increase in Egg #1 drop, we should decrease Egg #2 drops to minimize worst case number. so if we drop Egg #1 from xth floor initially, then in next turn we should try x + (x-1)th floor(to keep the worst case number same).
Thus we can say X + (x-1) + (x-2)…1 = 100
X(X+1)/2 = 100 => X=14.
So we should drop Egg #1 from 14th, then 27th, then 39th and so on.
Second thought is to try xth floor then 2xth floor till 100th, in this case worst case time will be (100/x)+(x-1). worst case will be when Egg #1 breaks at 100th floor then we have to try Egg #2 from (100-x)th to 99th floors. In (100/x) + (x-1) equation, with increase in x, 100/x decreases while (x-1) increases, thus we can minimize it when 100/x = (x-1), this gives x ~10, which gives worst case number as 19 drops.
But increasing the floor every time by x is not a very nice idea, as with each new increase in Egg #1 drop, we should decrease Egg #2 drops to minimize worst case number. so if we drop Egg #1 from xth floor initially, then in next turn we should try x + (x-1)th floor(to keep the worst case number same).
Thus we can say X + (x-1) + (x-2)…1 = 100
X(X+1)/2 = 100 => X=14.
So we should drop Egg #1 from 14th, then 27th, then 39th and so on.
swathi108:
ok
Answered by
0
heya..
Drop the first egg from 50.If it breaks you can try the same approach for a 50-storey building (1 to 49) and try it from 25th floor. If it did not break try at 75th floor. And use linear search with the remaining portion of storey we need to test. For example if the first egg breaks at 50 we need to try all possibilities from 1 to 49.
Now this looks a feasible solution. In computer student's jargon do a binary search with first egg and linear search with the second one. Best case is log (100) and worst is 50.
Now the optimal solution for the problem is that you figure out that you will eventually end up with a linear search because you have no way of deciding the highest floor with only one egg (If you broke one egg and you have to find the answer among 10 all you can do is start from the lowest to the highest and the worst is the total number of floors). So the whole question grinds up to how to make use of the first egg to reduce the linear testing of the egg.
Now let x be the answer we want, the number of drops required.
So if the first egg breaks maximum we can have x-1 drops and so we must always put the first egg from height x. So we have determined that for a given x we must drop the first ball from x height. And now if the first drop of the first egg doesn’t breaks we can have x-2 drops for the second egg if the first egg breaks in the second drop.
Taking an example, lets say 16 is my answer. That I need 16 drops to find out the answer. Lets see whether we can find out the height in 16 drops. First we drop from height 16,and if it breaks we try all floors from 1 to 15.If the egg don’t break then we have left 15 drops, so we will drop it from 16+15+1 =32nd floor. The reason being if it breaks at 32nd floor we can try all the floors from 17 to 31 in 14 drops (total of 16 drops). Now if it did not break then we have left 13 drops. and we can figure out whether we can find out whether we can figure out the floor in 16 drops.
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).
tysm.........@kundan
Drop the first egg from 50.If it breaks you can try the same approach for a 50-storey building (1 to 49) and try it from 25th floor. If it did not break try at 75th floor. And use linear search with the remaining portion of storey we need to test. For example if the first egg breaks at 50 we need to try all possibilities from 1 to 49.
Now this looks a feasible solution. In computer student's jargon do a binary search with first egg and linear search with the second one. Best case is log (100) and worst is 50.
Now the optimal solution for the problem is that you figure out that you will eventually end up with a linear search because you have no way of deciding the highest floor with only one egg (If you broke one egg and you have to find the answer among 10 all you can do is start from the lowest to the highest and the worst is the total number of floors). So the whole question grinds up to how to make use of the first egg to reduce the linear testing of the egg.
Now let x be the answer we want, the number of drops required.
So if the first egg breaks maximum we can have x-1 drops and so we must always put the first egg from height x. So we have determined that for a given x we must drop the first ball from x height. And now if the first drop of the first egg doesn’t breaks we can have x-2 drops for the second egg if the first egg breaks in the second drop.
Taking an example, lets say 16 is my answer. That I need 16 drops to find out the answer. Lets see whether we can find out the height in 16 drops. First we drop from height 16,and if it breaks we try all floors from 1 to 15.If the egg don’t break then we have left 15 drops, so we will drop it from 16+15+1 =32nd floor. The reason being if it breaks at 32nd floor we can try all the floors from 17 to 31 in 14 drops (total of 16 drops). Now if it did not break then we have left 13 drops. and we can figure out whether we can find out whether we can figure out the floor in 16 drops.
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).
tysm.........@kundan
Similar questions