And what about binary search? On Wed, Jul 6, 2011 at 12:26 PM, 991 <guruprakash...@gmail.com> wrote:
> Sorry abt the previous post ( and this one ) if it ended up as a spam. > I just saw the question and left the place. When I finished posting, > ppl hav already given replies... > > On Jul 7, 12:12 am, 991 <guruprakash...@gmail.com> wrote: > > 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. > > -- -Aakash Johari (IIIT Allahabad) -- 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.
