Aha! here is the other part: http://en.wikipedia.org/wiki/Floyd's_cycle-finding_algorithm
On Aug 24, 2:11 am, wbspresslyjr <[EMAIL PROTECTED]> wrote: > Oops -- for approach 1. down here, I meant to say that the hash table > breaks the constant space requirement... I guess I got ahead of > myself :) (this also applies to sets, and about any other data > structure in general)... > > On Aug 24, 1:00 am, wbspresslyjr <[EMAIL PROTECTED]> wrote: > > > > > I've heard this problem stated as such: assume you have an array of N > > numbers, each ranging on the interval [1,N-1], only one of these > > elements repeating in Read-Only memory. You only have O(1) (constant) > > "scratch" space to work with, and you need the algorithm to run in > > O(n) time. > > > There were many approaches mentioned here that I do not think are > > quite right -- > > > 1. any attempt to hash the value means your algo runs in O(nlog(n)) > > time (low bound by sorting) > > 2. any attempt to perform arithmetic on the numbers (like adding all > > of the numbers in your array and then subtracting 1 to n-1 -- this > > will get you a solution) requires O(log(n)) space (to store the > > numbers) > > > Thus, you need a solution that uses some kind of pointers (static size > > by definition), and a clever walk through the data. So it turns out I > > hve one of the two for you... in each location, walk to the index of > > its value... every walk will end up in a loop of two varieties: 1. it > > loops back to where it began, or 2. it loops because of the repeating > > element. if you do this on the last element (to wit array[N]), you > > will see something interesting... > > > What this does is that it shows you the connected components of these > > graphs... there will be one connected component that always shows the > > repeating element. Now you just have to find the repeater in linear > > time, constant space. > > > Pos Val > > 1 4 > > 2 1 > > 3 1 > > 4 2 > > 5 9 > > 6 8 > > 7 5 > > 8 7 > > 9 6 > > 10 3 > > ------------- > > 1 -> 4 -> 2 -> 1 > > 2 -> 1 -> 4 -> 2 > > 3 -> 1 -> 4 -> 2 -> 1 > > 4 -> 2 -> 1 -> 4 > > 5 -> 9 -> 6 -> 8 -> 7 -> 5 > > 6 -> 8 -> 7 -> 5 -> 9 -> 6 > > 7 -> 5 -> 9 -> 6 -> 8 -> 7 > > 8 -> 7 -> 5 -> 9 -> 6 -> 8 > > 9 -> 6 -> 8 -> 7 -> 5 -> 9 > > 10 -> 3 -> 1 -> 4 -> 2 -> 1 > > > On Aug 16, 1:41 pm, dsha <[EMAIL PROTECTED]> wrote: > > > > Hi there, > > > > I'm interested in the following problem: there is an array of integers > > > that contains each element only once except for one element that > > > occurs exactly twice. Is there a way to find this element faster than > > > O(n*log n) and with constant extra memory? If no, how can I prove it? > > > > Thanks in advance for ideas.- Hide quoted text - > > > - Show quoted text -- Hide quoted text - > > - Show quoted text - --~--~---------~--~----~------------~-------~--~----~ 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 -~----------~----~----~----~------~----~------~--~---
