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. --~--~---------~--~----~------------~-------~--~----~ 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 -~----------~----~----~----~------~----~------~--~---
