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 - --~--~---------~--~----~------------~-------~--~----~ 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 [EMAIL PROTECTED] For more options, visit this group at http://groups.google.com/group/algogeeks -~----------~----~----~----~------~----~------~--~---
