If the array A{1..n] contains integers in the range 1 to n-2, so that
the pigeonhole principle implies that there is at least one integer
that is duplicated in the array, then finding that duplicate entry is
equivalent to finding a node in a linked list at which a loop starts.
A solution for this problem, using fast and slow pointers, is given in
another thread in this group.Dave On Jan 15, 9:21 pm, nphard nphard <[email protected]> wrote: > Given an array of integers of size 'n' - consisting of 'n-2' unique integers > and 1 integer with a duplicate, find the repeated element in O(n). > > Note: This is a converse of finding the unique element in an array > consisting of duplicates - which can be solved with the XOR technique - but > I am not sure if the same/similar technique can be applied here. -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to [email protected]. To unsubscribe from this group, send email to [email protected]. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
