You have absolutely identical 2 eggs and empty K-story building. You can throw eggs from any floor and see if it was broken or not. If not, you can reuse it again momentarily. You need to identify the lowest floor, starting from which eggs is broken if thrown (”breaking floor”) in minimum possible steps in worst case.
Answers and Comments
1. Let's take N for the answer
2. The best choice will be to start with floor N first.
- if the egg breaks, do a linear search starting from 1 to N-1, guaranteeing a solution in N attempts.
- else go to N + (N-1) floor…
3. Continuing in this way, with N attempts, we can cover sum(N + N-1 + N-2… 2 + 1) floors.
Thus the answer is min{N} to yield N *(N+1)/2 > K
So, for example, for K=100, then N=14
2. The best choice will be to start with floor N first.
- if the egg breaks, do a linear search starting from 1 to N-1, guaranteeing a solution in N attempts.
- else go to N + (N-1) floor…
3. Continuing in this way, with N attempts, we can cover sum(N + N-1 + N-2… 2 + 1) floors.
Thus the answer is min{N} to yield N *(N+1)/2 > K
So, for example, for K=100, then N=14
Saved Stories
- What are the advantages of the demat account?
- Tell us about the last time you lost your temper? Did you take personal accountability for this situation?
- What is GAAP? Name at least three of the principles
- Can a Silverlight application create or change Office Documents via Open XML?
- How would you sort a linked list?
Sponsored Categories
One might try throwing the first egg from successive multiple-of-three floors until the egg breaks. Now you know that the lowest breaking floor is either the floor from which you just threw it or one of the two you skipped (because you already threw an egg from three floors below and it didn't break). However, throwing the second egg from either of the skipped floors doesn't always tell you about the remaining skipped floor.