This problem does not seem to have a O(n) time solution in the general case because it is a version of the Element uniqueness problem ( http://en.wikipedia.org/wiki/Element_distinctness_problem) which has a proven tight asymptotic bound of *n log n*.
On Sun, Jan 16, 2011 at 11:17 PM, awesomeandroid <priyaranjan....@gmail.com>wrote: > 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. > > -- 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.
