@gene: can you do dry run a test case: a[0]-a[n-1] 0 1 2 31 34 135
and if u c On Tue, Dec 7, 2010 at 8:55 AM, Gene <gene.ress...@gmail.com> wrote: > I should have mentioned that this problem only makes sense if the > array values must be unique. > > On Dec 6, 8:20 pm, Gene <gene.ress...@gmail.com> wrote: > > You guys are working too hard. Think about the sequence of numbers > > [ A[i] - i | i = 0,1,2,...n-1 ]. You are trying to probe this > > sequence to find the number of zeros. If you think about it for a > > while, you will see that this sequence is non-decreasing. It must be > > a segment of zero or more negative numbers followed by a segment of > > zero or more zeros followed by a segment of zero or more positive > > numbers. Therefore you can easily use two binary searches to find the > > index of the leftmost and rightmost zeros. This identifies all the > > elements where A[i]=i in O(2 log n) = O(log n) time. Of course if the > > searches fail, you have no elements at all where A[i]=i. > > > > On Dec 5, 9:46 am, Nikhil Agarwal <nikhil.bhoja...@gmail.com> wrote: > > > > > > > > > @Divesh I have updated my algo and Array A[1,2,3.....n] is sorted with > > > unique elements.CALL FIND_EQUAL(A,1,n) > > > > > int FIND_EQUAL(A,start,end) > > > 1.Go to the middle element > > > 2. If A[mid]>mid) > > > 3. if(start==mid) > > > 4 return mid-1; > > > 5 return FIND_EQUAL(A,1,mid-1); > > > 6 if(A[mid]=mid) > > > 7 if(mid==end) > > > 8 return mid; > > > 9 return FIND_EQUAL(A,mid+1,end); > > > > > On Sun, Dec 5, 2010 at 7:36 PM, coolfrog$ > > > <dixit.coolfrog.div...@gmail.com>wrote: > > > > > > @Nikhil > > > > run you algo .. > > > > on test case > > > > index -> 1 2 3 4 5 > > > > value -> 1 2 3 4 5 > > > > > > ouput is mid+1= 3+1=4 > > > > but it should be 5... > > > > correct me if i am wrong... and u have assumed all are positive, > hence > > > > base index should be 1 > > > > > > On Sun, Dec 5, 2010 at 4:41 PM, Nikhil Agarwal < > nikhil.bhoja...@gmail.com>wrote: > > > > > >> If All the elements are unique and sorted in ascending order then we > can > > > >> design an algorithm for O(lgn) and all nos are positive. > > > > > >> Run FIND_EQUAL(A,0,N-1) [A0,A1 and A2 are the array elements] > > > > > >> FIND_EQUAL(A,start,end) > > > >> 1.Go to the middle element > > > >> 2.If A[mid]==mid) > > > >> return mid+1; > > > >> if(A[mid]>mid) > > > >> then FIND_EQUAL(A,start,mid-1) > > > >> else > > > >> FIND_EQUAL(A,mid+1,end) > > > > > >> Runs in O(lgn) > > > > > >> On Sun, Dec 5, 2010 at 12:20 PM, jai gupta <sayhelloto...@gmail.com > >wrote: > > > > > >>> Any algorithm must in worst case lead to O(n) if the elements are > not > > > >>> unique. Take the case: > > > >>> 1 2 3 4 5 6 > > > >>> as all the elements satisfy the condition of of key==index . we > must go > > > >>> someway to each element. > > > >>> Hence O(n). > > > > > >>> This may be somehow made less if the element are given to be unique > by > > > >>> using heap. > > > > > >>> -- > > > >>> You received this message because you are subscribed to the Google > Groups > > > >>> "Algorithm Geeks" group. > > > >>> To post to this group, send email to algoge...@googlegroups.com. > > > >>> To unsubscribe from this group, send email to > > > >>> algogeeks+unsubscr...@googlegroups.com<algogeeks%2bunsubscr...@googlegroups.com> > <algogeeks%2bunsubscr...@googlegroups .com> > > > >>> . > > > >>> For more options, visit this group at > > > >>>http://groups.google.com/group/algogeeks?hl=en. > > > > > >> -- > > > >> Thanks & Regards > > > >> Nikhil Agarwal > > > >> Senior Undergraduate > > > >> Computer Science & Engineering, > > > >> National Institute Of Technology, Durgapur,India > > > >>http://tech-nikk.blogspot.com > > > >>http://beta.freshersworld.com/communities/nitd > > > > > >> -- > > > >> You received this message because you are subscribed to the Google > Groups > > > >> "Algorithm Geeks" group. > > > >> To post to this group, send email to algoge...@googlegroups.com. > > > >> To unsubscribe from this group, send email to > > > >> algogeeks+unsubscr...@googlegroups.com<algogeeks%2bunsubscr...@googlegroups.com> > <algogeeks%2bunsubscr...@googlegroups .com> > > > >> . > > > >> For more options, visit this group at > > > >>http://groups.google.com/group/algogeeks?hl=en. > > > > > > -- > > > > *Divesh* > > > > (¨`·.·´¨) Always > > > > `·.¸(¨`·.·´¨ ) Keep > > > > (¨`·.·´¨)¸.·´Smiling! > > > > `·.¸.·´" Life can give u 100's of reason 2cry,but u can give life > 1000's > > > > > > of reasons 2Smile" > > > > > > -- > > > > You received this message because you are subscribed to the Google > Groups > > > > "Algorithm Geeks" group. > > > > To post to this group, send email to algoge...@googlegroups.com. > > > > To unsubscribe from this group, send email to > > > > algogeeks+unsubscr...@googlegroups.com<algogeeks%2bunsubscr...@googlegroups.com> > <algogeeks%2bunsubscr...@googlegroups .com> > > > > . > > > > For more options, visit this group at > > > >http://groups.google.com/group/algogeeks?hl=en. > > > > > -- > > > Thanks & Regards > > > Nikhil Agarwal > > > Senior Undergraduate > > > Computer Science & Engineering, > > > National Institute Of Technology, > Durgapur,Indiahttp://tech-nikk.blogspot.comhttp:// > beta.freshersworld.com/communitie... > > -- > You received this message because you are subscribed to the Google Groups > "Algorithm Geeks" group. > To post to this group, send email to algoge...@googlegroups.com. > To unsubscribe from this group, send email to > algogeeks+unsubscr...@googlegroups.com<algogeeks%2bunsubscr...@googlegroups.com> > . > For more options, visit this group at > http://groups.google.com/group/algogeeks?hl=en. > > -- Thanks & Regards Nikhil Agarwal Senior Undergraduate Computer Science & Engineering, National Institute Of Technology, Durgapur,India http://tech-nikk.blogspot.com http://beta.freshersworld.com/communities/nitd -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to algoge...@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.
