Problem:
You have a staircase and 2 eggs. The staircase is N steps long. You can drop eggs on this staircase at any point between 0 to N. At a point X on the staircase where X >0 and X < N the eggs begin to break. Your mission, if you choose to accept it, it to find the point X in this staircase by making a minimum number of drops.
O O Step 0
|_
...|_
.......|_
..........|_ - The random point X where the egg breaks
..............|_
..................|_
Analysis:
Solution 1: Ugly
The easiest thing to do is to drop the egg at each step and check if it breaks. The worst case running time of such an algorithm is O(N). However there must be a reason we have 2 eggs to solve this problem. So obviously this is not the optimal solution. Lets think a little more.
Solution 2: A lil better
What can we do to use both the eggs ? Hmmm... Lets do this. Take egg 1 and drop it on odd steps. If it breaks then take the other egg and break it on the last even step before the step where egg1 broke. That is if egg 1 broke at step 5, drop egg 2 on step 4 (last even number before 5). If egg 2 breaks then you know that point is X (since the egg did not break at N=3). If it does not break then you know X is the number where egg 1 broke.
The efficiency of this solution is O(N/2) ~ O(N). But we can do better
Solution 3: I will leave it to you to figure this one out
Its possible to have an efficiency of something better than O(N) for this problem. With the last solution the egg can be dropped at odd intervals. What if we can drop the egg at an interval Z ? How will that help us determine the value of X ? Think about that. How should egg 2 be dropped so that for any interval Z, the value of X can be ascertained.
Performance:
To determine the performance for solution 3, consider making an equation F(Z). F(Z) is a function that determines the number of times (worst case) an egg must be dropped to determine the value of X.
Hint: F(Z) contains 2 component. One that is relevant before egg 1 breaks and one that is relevant after egg 1 breaks.
Once you have this equation in place you can determine the best running time for the worst scenario quite easily.
Hint: Differentiation. F(Z)' and F(Z)''.
This problem can be used to solve some practical difficulties. For example you know that you are to receive a 1024 bit number whose values you must calculate. You know that this number is formatted like so 0000000001111111... but you dont know where the 1s begin. This is like the staircase problem. Applying solution 3 can save time and allow you to quickly calculate the 2nd power of the 1024 bit number.
Subscribe to:
Post Comments (Atom)
Linear is good(Even-Odd), but not the best
ReplyDelete============================================
1. Divide your total number of floors into some segments, question is how to do the segments, my idea is take the sqrt(no_of_floors), say you have 100 stairs with you, so at the end of the day you will have 10 segments/blocks (sqrt(100)).
2. Use one egg for end-edge only, aka for stairs 0,10,20,30 and so on.
3. If first egg breaks at 20, we eventually know that it not got dusted on stair no 10, use a linear approach then from stair 11 to 19 with the second egg.
Not convinced? Well, complexity can be computed like:
First egg can drop max of sqrt(no_of_stairs) times, and eventually the second egg can drop at max that no of times too since it is dropping within the division.
so complexity will be around O(sqrt(n) * 2)
2.