We have two eggs,so have only two chances of missing.SO its about a combination of binary and linear search.
On Thu, Jul 7, 2011 at 9:09 AM, Aakash Johari <aakashj....@gmail.com> wrote: > 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. > -- Saurabh Singh B.Tech (Computer Science) MNNIT 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.
