Problem Statement
The two egg problem is as follows: there is a building with 100 floors. You are given 2 identical eggs. How do you use 2 eggs to find the threshold floor, where the egg will definitely break from any floor above floor N, including floor N itself.
Solution
Note that:
- We have to minimize the number of attempts it will take to find the threshold
- We have to maximize the jump for egg1 while keeping number of attempts minimum
Approach – 1
Let x = floor no. for the first drop and subsequent jump if first egg breaks at this floor then this becomes a one egg problem. We need to find the maximum attempts taken or the worst case scenario. eg: if x = 20 then at his level no. of attempts = 1 + 19 = 20 (if egg 1 breaks here)
So, in worst case scenario, no. of attempts = 100/x + (x-1) = F(x)
This is a curve, we need to take a derivative of the curve to find the minima:
dy/dx = 100(-1.x-2) + 1 = 0
=> -100/x2 + 1 = 0
=> x = 10
So in the worst case scenario i.e. When the first egg breaks at floor = 100, max attempts needed are 100/10 + (10-1) = 19
1 | floor 10 | attempts = 1 + 9 = 10
2 | floor 20 | attempts = 2 + 9 = 11
3 | floor 30 | attempts = 3 + 9 = 12
4 | floor 40 | attempts = 4 + 9 = 13
5 | floor 50 | attempts = 5 + 9 = 14
6 | floor 60 | attempts = 6 + 9 = 15
7 | floor 70 | attempts = 7 + 9 = 16
8 | floor 80 | attempts = 8 + 9 = 17
9 | floor 90 | attempts = 9 + 9 = 18
10 | floor 100 | attempts = 10 + 9 = 19
Do you see a problem with this approach? Are we not differentiating a variable that is not continuous? Lets try another approach!
APPROACH – 2
In every subsequent jump, number of attempts for egg 2 should decrease by one coz no. of attempts for egg 1 increased by 1. Lets make an equation from jumps possible for egg 1
x - 0 -> start at floor x
+ x - 1 -> jump to floor x + (x - 1) ... eg floor 29
+ x - 2
...
+ x - x -> last floor jump - this cannot be more than 100
Summing it up will give us the following:
=> x.x + x - [1 + 2 + .. + x] <= 100
=> x2 + x - [x.(x + 1) / 2] <= 100
=> 2x2 + 2x - x2 - x <= 200
=> x2 + x - 200 <= 0
this gives 13 < x < 14
lets take x = 14
1 | floor 14 | attempts = 1 + 13 = 14
2 | floor 14+13 = 27 | attempts = 2 + 12 = 14
3 | floor 27+12 = 39 | attempts = 3 + 11 = 14
4 | floor 39+11 = 50 | attempts = 4 + 10 = 14
5 | floor 50+10 = 60 | attempts = 5 + 9 = 14
6 | floor 60+9 = 69 | attempts = 6 + 8 = 14
7 | floor 69+8 = 77 | attempts = 7 + 7 = 14
8 | floor 77+7 = 84 | attempts = 8 + 6 = 14
9 | floor 84+6 = 90 | attempts = 9 + 5 = 14
10 | floor 90+5 = 95 | attempts = 10 + 4 = 14
11 | floor 95+4 = 99 | attempts = 11 + 3 = 14
Here, we discard approach-1, although its only due to this approach we were able to make progress to approach-2.