This one was one of the widely discussed problems on the campus during my stay @ IIT Kharagpur.
Question:
You are given 2 eggs. Both eggs have same properties.
These 2 eggs are very strong. Just by dropping them on the floor they won't break.
They have a limit - in a way - if they are dropped from a particular height or more, then they will break.
With two eggs and a building with 100 floors, what is the optimal strategy for finding the lowest floor at which an egg will break when dropped ? meaning - find minimum number of drops by which we can find the lowest floor at which an egg will break when dropped.
Understanding the problem and some experimentation:
As it is said in the problem both the eggs have same properties - meaning - if egg#1 starts to break (let's say) at building 25 then egg#2 will also follow the same behavior.
Trial 1:
now let's say, we choose 25th floor to drop the 1st egg.
If, 1st egg breaks when dropped from 25th floor, then we have to start from 1st floor for 2nd egg (to find out exactly from which floor that egg starts to break).
in worst case we will end up dropping from floor 1 to (25-1). So, total number of attempts will be 1+24 = 25 in this case.
But, what if 1st egg does not break at 25th floor ?
Trial 2:
let's say, we split 100 floors in 10 chunks.
1-10, 11-20, 21-30, ..., 91-100
We start from 10th floor.
If egg breaks, then we start from floor 1-9. Total= 1+9 = 10.
If egg does not break, then in worse case - let's assume egg actually starts breaking at 99th floor.
This way it comes to
1(for 10th floor) +
1(for 20th floor) +
1(for 30th floor) +
... +
... +
1(for 90th floor) +
1(100th floor egg breaks) +
9 (to check if on 91st to 99th floor egg breaks or not)
Total : 10 + 9 = 19 attempts to just figure out that the egg actually starts breaking from 99th floor.
Trial 3:
Why don't we use binary search ?
For binary search we have to start at 50th floor. worst case will require 50 trials which is not optimal as our trail#2 requires only 19 attempts.
Correct Approach:
We just saw that our previous attempts did give some clues.
Now, let's assume that we start from floor x ; then if egg breaks at floor x then we have to try 1 to (x-1).
Can we choose (starting floor) x such that irrespective of egg breaks or not, x is actually the optimal floor to begin with ?
Example,
let's assume that x = 20.
So,
Attempt#1, drop egg from floor 20 (egg does not break)
Attempt#2, drop egg from floor 39 [ (20 + ( 20-1)) - so if egg does not break, and we know that 20 is the optimal attempts. so we have to choose 39th floor. so if at 39th floor egg breaks (we have already wasted 2 attempts at this moment) we know that we can start from 21st to 38th floor to check if egg breaks or not]
...
...
so on...
I hope, you get the idea behind the previous example.
Now, let's get to the core logic..
Let's assume that x is our optimal floor number to start dropping the egg.
so, using this, if egg breaks or not we should be able to figure out ( using next (x-1) attempts ) that from which floor egg starts to break.
worse case analysis...
x (egg to be dropped from xth floor - egg does not break) +
x-1 (egg to be dropped from (x+x-1)th floor - egg does not break) +
x-2 (egg to be dropped from (x+x-1+x-2)th floor - egg does not break)
... +
... +
3 + 2 + 1 = x(x+1)/2
These all attempts should cover all 100 floors.
so, our equation looks like this ( x . (x+1) ) / 2 <= 100
and x = 13.65 ~ 14
Hence, 14th floor should be the floor we should start dropping the 1st egg and hence our optimal attempts are 14 !
---
This equation does give us a generalized formula for n number of floors.
x.(x+1)/2 = n
My todo question is: Can we have a generalized formula for M eggs and a building with N floors ?
Question:
You are given 2 eggs. Both eggs have same properties.
These 2 eggs are very strong. Just by dropping them on the floor they won't break.
They have a limit - in a way - if they are dropped from a particular height or more, then they will break.
With two eggs and a building with 100 floors, what is the optimal strategy for finding the lowest floor at which an egg will break when dropped ? meaning - find minimum number of drops by which we can find the lowest floor at which an egg will break when dropped.
Understanding the problem and some experimentation:
As it is said in the problem both the eggs have same properties - meaning - if egg#1 starts to break (let's say) at building 25 then egg#2 will also follow the same behavior.
Trial 1:
now let's say, we choose 25th floor to drop the 1st egg.
If, 1st egg breaks when dropped from 25th floor, then we have to start from 1st floor for 2nd egg (to find out exactly from which floor that egg starts to break).
in worst case we will end up dropping from floor 1 to (25-1). So, total number of attempts will be 1+24 = 25 in this case.
But, what if 1st egg does not break at 25th floor ?
Trial 2:
let's say, we split 100 floors in 10 chunks.
1-10, 11-20, 21-30, ..., 91-100
We start from 10th floor.
If egg breaks, then we start from floor 1-9. Total= 1+9 = 10.
If egg does not break, then in worse case - let's assume egg actually starts breaking at 99th floor.
This way it comes to
1(for 10th floor) +
1(for 20th floor) +
1(for 30th floor) +
... +
... +
1(for 90th floor) +
1(100th floor egg breaks) +
9 (to check if on 91st to 99th floor egg breaks or not)
Total : 10 + 9 = 19 attempts to just figure out that the egg actually starts breaking from 99th floor.
Trial 3:
Why don't we use binary search ?
For binary search we have to start at 50th floor. worst case will require 50 trials which is not optimal as our trail#2 requires only 19 attempts.
Correct Approach:
We just saw that our previous attempts did give some clues.
Now, let's assume that we start from floor x ; then if egg breaks at floor x then we have to try 1 to (x-1).
Can we choose (starting floor) x such that irrespective of egg breaks or not, x is actually the optimal floor to begin with ?
Example,
let's assume that x = 20.
So,
Attempt#1, drop egg from floor 20 (egg does not break)
Attempt#2, drop egg from floor 39 [ (20 + ( 20-1)) - so if egg does not break, and we know that 20 is the optimal attempts. so we have to choose 39th floor. so if at 39th floor egg breaks (we have already wasted 2 attempts at this moment) we know that we can start from 21st to 38th floor to check if egg breaks or not]
...
...
so on...
I hope, you get the idea behind the previous example.
Now, let's get to the core logic..
Let's assume that x is our optimal floor number to start dropping the egg.
so, using this, if egg breaks or not we should be able to figure out ( using next (x-1) attempts ) that from which floor egg starts to break.
worse case analysis...
x (egg to be dropped from xth floor - egg does not break) +
x-1 (egg to be dropped from (x+x-1)th floor - egg does not break) +
x-2 (egg to be dropped from (x+x-1+x-2)th floor - egg does not break)
... +
... +
3 + 2 + 1 = x(x+1)/2
These all attempts should cover all 100 floors.
so, our equation looks like this ( x . (x+1) ) / 2 <= 100
and x = 13.65 ~ 14
Hence, 14th floor should be the floor we should start dropping the 1st egg and hence our optimal attempts are 14 !
---
This equation does give us a generalized formula for n number of floors.
x.(x+1)/2 = n
My todo question is: Can we have a generalized formula for M eggs and a building with N floors ?
