if range is defined there are several methods discussed at http://aperiodic.net/phil/archives/Geekery/find-duplicate-elements.html
Regards Priyaranjan http://code-forum.blogspot.com On Jan 16, 11:35 pm, yq Zhang <zhangyunq...@gmail.com> wrote: > @Dave, your algorithm is a dijkstra cycle finding algo. It requires the > function to have only ONE SINGLE cycle in the transition function. However, > the transition function for the array could have several cycles. How could > you find the duplicate? Can you elaborate more on your solution? Maybe I > just didn't understand your solution. > > BTW, if it's guranteed the number is between 1...n-2. The simpleset approach > is SUM(array) - SUM(1...n-2) > > Thanks > > Yq > > > > > > > > On Sun, Jan 16, 2011 at 10:25 AM, Dave <dave_and_da...@juno.com> wrote: > > Okay. Here is a further exposition of the solution. It took me a while > > to remember where I had used it before. > > > i = n > > j = n > > do while not (i = j) > > i = A(A((i)) > > j = A(j) > > end > > /* Now a=b can be reached at either 2k or k steps from n, */ > > /* where k is some integer between 1 and n. */ > > i = n > > do while not (i = j) > > i = A(i) > > j = A(j) > > end > > print a > > > Dave > > > On Jan 16, 11:57 am, juver++ <avpostni...@gmail.com> wrote: > > > @Dave > > > Cycle finding algo (Floyd's, Brent's) can be applied only for the > > iterated > > > function values. > > > This means: f(x0) = x1; f(x1) = x2 and etc. > > > Suppose we have the following array: 1 2 3 2 4. Value 2 have two > > different > > > transitions. > > > > Clarify your proposed method if it needs additional observations. > > > -- > > 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<algogeeks%2Bunsubscribe@googlegroups > > .com> > > . > > For more options, visit this group at > >http://groups.google.com/group/algogeeks?hl=en. -- 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.
