|
|
back to boardIs my algorithm correct? If not give me a hint! I thought that tha fastest way we could determine the floor was a binary search. For each i=1,n as long as we have enough eggs we do the binary search and stop when we visited both i and i-1. If we are left with only one egg we can't risk breaking without knowing the floor it so we start from the value just below the smallest value we know the egg hasn't broken and check all of them until we break the egg. For each binary search we count how many tests we did and just select the largest one (worst case). The complexity is O(N*log2 N). Is this correct or am I mistaken somewhere? And can anyone give me some test cases please? Re: Is my algorithm correct? If not give me a hint! Posted by sylap 29 Aug 2013 02:53 Yes, binary search is good when you have enough eggs. But what if you don't have enough eggs? Then when you have 1 egg left you need to check all floors, from 1st to the topmost floor. For example: Case eggs=100 and floors=100 Then you will do 7 experiments I will do 7 experiments too But case eggs=2 and floors=100 Then you will do about ~1+50 experiments But I will do 14 (i'm too lazy to write how, sorry) |
|
|