Approach 1: Start from storey 1 and go up. keep dropping one of the eggs. As soon at it breaks, return the storey you are in now. No. of drops in the worst case: 99
Approach 2: Split the building into 10 '10 storeyed' parts. Start Dropping eggs at 10,20,30,...th storey. If it breaks at say 40th, use the other egg from 31st storey till 39th and return the ans. No. of drops in worst case: approx. 20 Approach 3: Why should v divide the building into equal storeyed segments? Have more storeys in lower part of the building and let it come down as we go up. How does it help? Well by the nature of our method, if it breaks at some 80+ storey (say), we want use the second egg lesser number of times that it was when it is in 20th storey or something. The first egg can be used in this order: 14,27,39,50,60... ( I am about to sleep now and I have no energy to find out the exact starting number. But I hope that u get the idea.) Now the same approach can be used once the first egg breaks. No. of drops in worst case: Approx. 14 More on this problem: Find an algo for any general number of eggs and any general number storeys... Dont look at the hint below before giving it a try. Hint: DP On Jul 6, 10:05 pm, shiv narayan <narayan.shiv...@gmail.com> wrote: > * 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 -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
