@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%2bunsubscr...@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.
