wu :: forums - Print Page


    
      
        wu :: forums
        (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi)
      

        riddles >> cs >> Finding repetitions in an array (constant space)
        
(Message started by: tseuG on Feb 6^th, 2004, 12:11pm)

Title: Finding repetitions in an array (constant space)
Post by tseuG on Feb 6^th, 2004, 12:11pm

You have a read-only array A[1..n] which is populated by numbers from 1..n-1, which implies atleast one repetition. However, there can be more. Find any one repeated number in linear time using constant space.

Title: Re: Finding repetitions in an array (constant spac
Post by John_Gaughan on Feb 6^th, 2004, 12:19pm

Is the array sorted, such that a_i >= a_i-1?

Title: Re: Finding repetitions in an array (constant spac
Post by tseuG on Feb 6^th, 2004, 4:51pm

No.

Title: Re: Finding repetitions in an array (constant spac
Post by towr on Feb 7^th, 2004, 4:40am

if there was exactly one repetition you could find the answer by adding all the numbers and subtract n(n-1)/2

Title: Re: Finding repetitions in an array (constant spac
Post by tseuG on Feb 7^th, 2004, 8:32am

Yes. However, in this case, the repetitions can be more than one (and there has to be atleast one).

Title: Re: Finding repetitions in an array (constant spac
Post by John_Gaughan on Feb 7^th, 2004, 11:41pm

So we have an array of arbitrary length, unsorted, and we need to find the duplicates. Furthermore, the algorithm must be O(1) and use a fixed amount of space. Okay, the space requirement is possible, although it would be tight. But searching an unsorted array in O(1) time is impossible. Even O(log(n)) is tough for unsorted data, but it depends on the application.

This means that the algorithm cannot depend on the size of the array, so it cannot search all the elements or even a subset of elements that depends on the size of the array (like n/2 elements or log(n) elements). So, without searching all of the unsorted elements, I have to find the duplicates.

I'm stuck, anyone else have an idea?

Title: Re: Finding repetitions in an array (constant spac
Post by tseuG on Feb 8^th, 2004, 7:10am

The algorithm can depend on the size of the array. I never said O(1) is the constraint for time. It's the space that has to be constant. The algorithm has to run in linear time O(n).

Title: Re: Finding repetitions in an array (constant spac
Post by towr on Feb 8^th, 2004, 7:49am

::[hide]I'm thinking, swap..
start with a[1], swap a[1] with a[a[1] untill a[1]=1, then go on with a[2] etc.
at some point you'll have an a[k]=m and a[m]=m (m!=k) and thus a repetition..
(It needs to be fleshed out a bit more, but I'm sure you get the gest)[/hide]::

Title: Re: Finding repetitions in an array (constant spac
Post by DH on Feb 8^th, 2004, 8:29am

Are we allowed to change A ?

Title: Re: Finding repetitions in an array (constant spac
Post by tseuG on Feb 8^th, 2004, 9:02am

towr, could you explain your solution in more detail? How is the final condition [hide] a[m] = m and a[k] = m (k!=m)[/hide] going to be checked so that the total time is still linear? Further, the array should not be modified. Sorry for missing that in my first post.

Title: Re: Finding repetitions in an array (constant spac
Post by towr on Feb 8^th, 2004, 10:05am

Here's a MOO-version of the algorithm

Code:

a=args;
n=length(a);

for i in [1..n]
while (a[i] != i)
s=a[i];
if(a[s] != s)
a[i]=a[s];
a[s]=s;
else
return s;
endif
endwhile
endfor

There are at most 2n comparisons: once for every number not in it's own place and once after it has been put there. (Of course it must be less than 2n unless there are no repetitions)

Of course if we can't change a, then this is moot.. Still I think it's a nice solution.

Title: Re: Finding repetitions in an array (constant spac
Post by towr on Feb 8^th, 2004, 10:41am

Here's another nice but tricky solution..
Take the product of (the first) n primes, [prod]_i=1ⁿprime_i, and then for i from 1 to n divide by prime_a[i] until this doesn't yield an integer..
The tricky part is justifying where you get those n primes.. :P

Title: Re: Finding repetitions in an array (constant spac
Post by John_Gaughan on Feb 8^th, 2004, 6:20pm

on 02/08/04 at 07:10:40, tseuG wrote:

The algorithm can depend on the size of the array. I never said O(1) is the constraint for time. It's the space that has to be constant. The algorithm has to run in linear time O(n).

Sorry, I just reread the original post... hooked on phonics didn't work for me ;-)

Title: Re: Finding repetitions in an array (constant spac
Post by Barukh on Feb 9^th, 2004, 5:56am

That's a great puzzle! All my friends to whom I presented it, are blowing their brains ;D

on 02/08/04 at 09:02:57, tseuG wrote:

Further, the array should not be modified. Sorry for missing that in my first post.

tseuG, let me clarify this point: do you mean no changes are allowed in the array, or that the contents should be the same at the end of the algorithm (that is more relaxed)?

Title: Re: Finding repetitions in an array (constant spac
Post by Barukh on Feb 9^th, 2004, 5:58am

on 02/08/04 at 10:41:11, towr wrote:

I don't think this product fits the constant space requirement either... ;)

Title: Re: Finding repetitions in an array (constant spac
Post by tseuG on Feb 9^th, 2004, 6:02am

Barukh, it's a read-only array.

Title: Re: Finding repetitions in an array (constant spac
Post by towr on Feb 9^th, 2004, 6:31am

on 02/09/04 at 05:58:15, Barukh wrote:

I don't think this product fits the constant space requirement either... ;)

meh, unlimited space seems constant enough :P
But seriously, without limitations on n, or the size of integers there's really no way to tell.. For unlimited n there will allways be these kinds of problems..

Title: Re: Finding repetitions in an array (constant spac
Post by Barukh on Feb 10^th, 2004, 6:12am

on 02/09/04 at 06:02:01, tseuG wrote:

Barukh, it's a read-only array.

Well, it seems at this point I will ask for a hint... :o

Title: Re: Finding repetitions in an array (constant spac
Post by Corleone on Feb 15^th, 2004, 12:59pm

This was another approach, I was thinking.

Start from a[1] and visit a[a[1] and then go on a[a[a[1]] until you visit the same index again.
Eg: A[1] = 2, A[2] = 4, A[4] = 6, A[6] = 2

Then you would be visiting A[2] twice in your path. Formally if you join the vertices i, a[i], a[a[i], if the path is a cycle that starts with i and traces back to i. You can say the repeated number is i. But this method will not work if you start with 1 and end up with 1 (where 1 is the index).

Ofcourse, still the storage space is of the order O(n) as you need atleast n bits to store if you have visited a particular index twice or not.

::

Title: Re: Finding repetitions in an array (constant spac
Post by John_Gaughan on Feb 15^th, 2004, 3:29pm

on 02/15/04 at 12:59:02, Corleone wrote:

This was another approach, I was thinking.

You have a good idea with treating it like a digraph. It would take linear memory, but I think you're on the right track.

Oh, you can hide text with the "hide /hide" tags. Just put that in square brackets. You don't need to color the text manually.

Title: Re: Finding repetitions in an array (constant spac
Post by NoNothing on Feb 23^rd, 2004, 9:40am

Tseug, thanks for this nice problem. And thanks for not hasting to post a solution. Here's a hint for those who want it:

::[hide]When I start my super_linear_time_const_space_find_rep_alg(), it starts iterating through the array (obviously). The hint is: it DOES matter which element it starts with. I mean the index.[/hide]::

Title: Re: Finding repetitions in an array (constant spac
Post by lovey on Feb 23^rd, 2004, 3:10pm

Lets say range is not given i.e if array elements are not in btn 1..n. Is there a soln keeping all constraints as the original problem ?

Title: Re: Finding repetitions in an array (constant spac
Post by Rezyk on Feb 24^th, 2004, 11:41pm

I believe this works:
[hide]int x = n, y = n;
do {x = A[A[x]; y = A[y];} while (x!=y);
x = n;
do {x = A[x]; y = A[y];} while (x!=y);
return x;[/hide]

Title: Re: Finding repetitions in an array (constant spac
Post by NoNothing on Feb 25^th, 2004, 6:06am

on 02/24/04 at 23:41:54, Rezyk wrote:

I believe this works:
[hide]int x = n, y = n;
do {x = A[A[x]; y = A[y];} while (x!=y);
x = n;
do {x = A[x]; y = A[y];} while (x!=y);
return x;[/hide]

Oh, no, you stole my code for super_linear_time_const_space_find_rep_alg()! Damn those opensource advocates.

Well, almost :-)

Title: Re: Finding repetitions in an array (constant spac
Post by Barukh on Feb 26^th, 2004, 1:13am

Brilliant!!! Bravo, Rezyk and NoNothing (who claims to be the inventor of the code ;D)!

By the way, can you prove that the code is correct? It's not obvious... I believe I've got a demonstration.

Title: Re: Finding repetitions in an array (constant spac
Post by NoNothing on Feb 26^th, 2004, 6:39am

on 02/26/04 at 01:13:13, Barukh wrote:

Brilliant!!! Bravo, Rezyk and NoNothing (who claims to be the inventor of the code ;D)!

By the way, can you prove that the code is correct? It's not obvious... I believe I've got a demonstration.

B.- you need to notice that if you start from the last element, the problem becomes akin to finding a loop in a single-linked list. Then you just apply a known solution. That's all *I* did. What I said before was a sco joke. Correctness is easy to prove, think about it.

Title: Re: Finding repetitions in an array (constant spac
Post by dont_get_it on Feb 29^th, 2004, 7:31am

on 02/24/04 at 23:41:54, Rezyk wrote:

I believe this works:
[hide]int x = n, y = n;
do {x = A[A[x]; y = A[y];} while (x!=y);
x = n;
do {x = A[x]; y = A[y];} while (x!=y);
return x;[/hide]

Perhaps i'm misunderstanding you but i am afraid that this will not work if we have repetition at the end. Example where we have 2 repetitions, one at the end:

1,2,1,4,4

Title: Re: Finding repetitions in an array (constant spac
Post by towr on Feb 29^th, 2004, 7:57am

Quote:

1,2,1,4,4

int x = n, y = n;
<x=5, y=5>

do {x = A[A[x]; y = A[y];
<x=4, y=4>
} while (x!=y);
<x=4, y=4>

x = n;
<x=5, y=4>

do {x = A[x]; y = A[y];
<x=4, y=4>
} while (x!=y);
<x=4, y=4>

return x;
<x=4>

seems to work for me..

Title: Re: Finding repetitions in an array (constant spac
Post by berry on Mar 11^th, 2004, 12:11pm

If the question is changed like n elements with range from 1 to n, there is one repition,then
the above alogroithem wont work.

for ex: 2, 2 , 3 , 4 ,5

Title: Re: Finding repetitions in an array (constant spac
Post by lovey on Mar 12^th, 2004, 7:12pm

for range 1..n & n elements ,
decrement x,y if x==A[x] in the first loop and decrement x in the second loop. This essentially finds the starting point of the linked list. :)

Title: Re: Finding repetitions in an array (constant spac
Post by Barukh on Mar 13^th, 2004, 4:45am

on 03/11/04 at 12:11:36, berry wrote:

If the question is changed like n elements with range from 1 to n, there is one repition, then the above alogroithem wont work.

for ex: 2, 2 , 3 , 4 ,5

If the condition is that there is at most one repetition, then an easy algorithm exists – see towr’s reply #3 in this thread.

on 03/12/04 at 19:12:03, lovey wrote:

for range 1..n & n elements ,
decrement x,y if x==A[x] in the first loop and decrement x in the second loop. This essentially finds the starting point of the linked list. :)

Can you elaborate on this please? I don’t see how this approach solves the problem in general.

Title: Re: Finding repetitions in an array (constant spac
Post by lovey on Mar 13^th, 2004, 9:37am

when the range is 1.. n-1 , starting from n ensures that u r not going to have a self loop ( A[x] == x) at the head. Self loop are okk after atleast one jump as the jump to x finds the repetition of x if x makes a self loop.

This doesnt apply to 1..n . Coz u can have a self loop at the head as seen in 2 2 3 4 5. Hence i suggested to decrement x,y so that we can start from an index that is not a self loop.

Title: Re: Finding repetitions in an array (constant spac
Post by Rezyk on Mar 13^th, 2004, 4:05pm

What happens with 2 1 5 5 4?

Title: Re: Finding repetitions in an array (constant spac
Post by lovey on Mar 13^th, 2004, 4:46pm

on 03/13/04 at 16:05:21, Rezyk wrote:

What happens with 2 1 5 5 4?

this is taken care by the original algo itself. and decrements would nt happen since (x=5) != (A[x] = 4). First loop returns with 5 and second loop returns the repeated number 5.

Title: Re: Finding repetitions in an array (constant spac
Post by Rezyk on Mar 13^th, 2004, 9:37pm

With the original algorithm, first loop would return 5 and second loop would return incorrect answer 4...still not sure how the modified algorithm would work.

What about 2 2 3 5 4?

Title: Re: Finding repetitions in an array (constant spac
Post by lovey on Mar 14^th, 2004, 9:44am

on 03/13/04 at 21:37:57, Rezyk wrote:

With the original algorithm, first loop would return 5 and second loop would return incorrect answer 4...still not sure how the modified algorithm would work.

What about 2 2 3 5 4?

ooooops !!!! finally took a pencil and realized my mistake. Sorry about the confusion. soln i gave doesnt work in general. the problem is to find a good starting point ( with n included array can have unreachable loops from the end w/o any repetition in them as disclosed by 2 2 3 5 4) . Is it even possible to use the SLL tactic when we are in range 1..n for n elements. ?

Title: Re: Finding repetitions in an array (constant spac
Post by Neelesh on Sep 17^th, 2004, 12:30am

Soltion seems to that it will not work if the any of the number is on the same index i.e. numner k on A[k].

Title: Re: Finding repetitions in an array (constant spac
Post by Neelesh Maurya on Sep 20^th, 2004, 10:51pm

First of all , I would liek u guys to tell that any O(n) time O(1) Space does not seem to exist for read only array.

yes if the Array is modifiable You can use following code for o(n),O(1)
int find_dup(int A[],int size )
{
int temp;
for(int i = 1; i <= size;i++)
{
A[i-1] < 0 ? temp = -A[i-1]:temp = A[i-1];
if(A[temp-1] < 0)
{
return temp;
}else
{
A[temp-1] = -A[temp-1];
}

}
return 0;

}

Title: Re: Finding repetitions in an array (constant spac
Post by Barukh on Sep 22^nd, 2004, 5:57am

on 09/17/04 at 00:30:56, Neelesh wrote:

Soltion seems to that it will not work if the any of the number is on the same index i.e. numner k on A[k].

Are you talking about the algorithm proposed by Rezyk and NoNothing (replies #20, #22)? I tried it on the following array: A = 1, 2, 3, 4, 4, and it worked just fine.

This algorithm obviously has linear time complexity, so your next post is also not clear...

Title: Re: Finding repetitions in an array (constant spac
Post by sujansunil on Sep 27^th, 2004, 9:43am

help me please..........
:-[
Can anyone help me out for designing a O(n log n) algorithm to determine whether an arbitrary sequence if 'n' integers contains repeated occurences of some number.

Title: Re: Finding repetitions in an array (constant spac
Post by John_Gaughan on Sep 27^th, 2004, 12:22pm

If you are not limited to constant space, you can insert each element of the array into a binary search tree. If there are any collisions, you know the elements that collide are duplicates. However, this will take linear space.

Title: Re: Finding repetitions in an array (constant spac
Post by towr on Sep 27^th, 2004, 1:13pm

If the sequence is given in an array you could just sort it and search for doubles, but that won't work for an arbitrarily large sequence of numbers.

Title: Re: Finding repetitions in an array (constant spac
Post by Vincent Lascaux on Nov 23^rd, 2004, 9:36am

Here is a demonstration I believe correct...
I define B as follow :
B[0] = n
B[i+1] = A[B[i] when i>=0

Since B takes a finit number of values, there must be some repetitions. I call k the smallest number so that B[k] is repeated. I call l the smallest number strictly larger than 1 so that B[k+l] = B[k].
k>0 (B[0] = n is not present in A and this cant be repeated)
I define the function f as follow :
f(i) = i if i<k and f(i) = k+(i-k)%l if i>=k
A simple recurrence shows that B[i] = B[f(i)] for every i
max f(i) = k+l-1 thus all B[f(i)] are distincts and B[f(i)] = B[f(j)] <=> B[i] = B[j] <=> f(i) == f(j) <=> (i<k and i=j) or (i>=k and j>=k and k+(i-k)%l = k+(j-k)%l) <=> (i<k and i=j) or (i>=k and j>=k and i-j = 0 mod l)

The first loop runs i times until x=y <=> B[2*i] = B[i] <=> (i<k and i=2i) or (i>=k and i=0 mod l) <=> i=0 or (i>=k and i=0 mod l)

i can't be 0 since the loop will run at least once (its a do while loop, not a while loop). So the first loop will stop after i0 iteration where i0 is the smallest multiple of l larger than k and not null

The second loop runs i times until x = y <=> B[i] = B[i0+i] <=> i>=k and i0=0 mod l <=> i>=k

After the execution, x = B[i] = B[k] = B[k+l] = A[B[k+l-1]

Since k>0, x = B[k] = A[B[k-1] = A[B[k+l-1]
B[k-1] != B[k+l-1] (because k is the *smallest* number so that B[k] is repeated). So x is a value repeated in A.

Title: Re: Finding repetitions in an array (constant spac
Post by Vincent Lascaux on Nov 23^rd, 2004, 9:41am

on 11/23/04 at 09:36:26, Vincent Lascaux wrote:

I call l the smallest number strictly larger than 1 so that B[k+l] = B[k].

I meant strictly positive 0:)

Title: Re: Finding repetitions in an array (constant spac
Post by puzzlecracker on Dec 8^th, 2004, 6:20pm

I am too SLOW -- can someone elaborate how and why does this work?

I believe this works:
int x = n, y = n;
do {x = A[A[x]; y = A[y];} while (x!=y);
x = n;
do {x = A[x]; y = A[y];} while (x!=y);
return x;

Title: Re: Finding repetitions in an array (constant spac
Post by cssomnath on Dec 12^th, 2004, 6:07am

As the A[n] =‚ n (The array contains elements between 1 c n-1) then A[n] contains some other element from 1 to n-1. Now starting from A[n] you can think of a linked list. Assume that A[n] points to k if A[n] = k. The linked list starting from A[n] must have a loop at the end as there are duplicate elements.

Proof: If there is no loop. Then there are no two nodes pointing to the same node. In that case the linked list starting from A[n] will be of length n and all n node will contain different values. Which is not true.

Now it just boils down to cycle detection algorithm in a linked list. You need to find out the start node of the cycle.

Now if you are wondering how the why the algo returns the start node of the loop you might like to give a look at the discussion (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi?board=riddles_cs;action=display;num=1027805014;start=18)

Title: Re: Finding repetitions in an array (constant spac
Post by Joe on Dec 13^th, 2004, 8:56am

I have the following algo that I know will work if there is
one repitition in the array:

find_repitition(A) {
sum = A.size*(A.size+1)/2;
for(int i=0;i<A.size;i++)
sum -= A[i];
return A.size-sum;
}
how this works:
the idea is:
we have in A n numbers from the range {1,2,...,n-1}, with
one repition (this means n = A.size).
let x be the one number that repeats in A.
this means that the sum of all the numbers in A
is 1+2+...+(n-1)+x.
fisrt we initialize sum to be 1+2+...+n = n*(n+1)/2
(by the known formula).
after the loop , sum is exactly
(1+2+...+n) - (1+2+...+(n-1)+x) = n-x.
this means that n-sum = n-(n-x) = x and this
is exactly what we return.

as for the case where there are 2 repititions, I
can't (atleast in the 5 minutes I thaught about it)
find a solution. but what exactly is the specification of
the problem: do we have an array of size n+1 with
all the numbers from range {1,2,...,n-1} with 2 repititions,
or something else?

by the way, this is a great site!

Title: Re: Finding repetitions in an array (constant spac
Post by puzzlecracker on Dec 13^th, 2004, 9:13am

Joe - this is trivial problem you've just described.

Title: Re: Finding repetitions in an array (constant spac
Post by puzzlecracker on Dec 16^th, 2004, 10:24pm

why do we need a second 'do', won't the 1st 'do' find the cycle?

Code:

int x = n, y = n;
do {x = A[A[x]]; y = A[y];} while (x!=y);
x = n;
do {x = A[x]; y = A[y];} while (x!=y);
return x;

Title: Re: Finding repetitions in an array (constant spac
Post by Grimbal on Dec 17^th, 2004, 12:47am

The first 'do' finds the cycle but it does not tell where we entered it. And it is only at the entry point that we have a repeat. The second 'do' uses information about the cycle length to find the place where we entered the loop.

Title: Re: Finding repetitions in an array (constant spac
Post by noname on Dec 18^th, 2005, 2:54am

on 09/27/04 at 12:22:14, John_Gaughan wrote:

Title: Re: Finding repetitions in an array (constant spac
Post by noname on Dec 18^th, 2005, 2:56am

Do you know what linear time means??

on 02/07/04 at 23:41:20, John_Gaughan wrote:

Title: Re: Finding repetitions in an array (constant spac
Post by algo_wrencher on Dec 23^rd, 2005, 12:20pm

It seems whenever an array with a range of elements is given, you can always sort it in O(n) time as:

void sort(int a[])
{
for(int i=0;i<n;i++)
{
if(a[i]>a[a[i] && a[i]>i)
swap(&a[i],&a[a[i]);
}
}

After sorting, u can compare any no. with its follower and in the worst case it wud be when the largest no. is repeating. So, ur job is done in O(n ) time... ;D

Title: Re: Finding repetitions in an array (constant spac
Post by KC on Apr 27^th, 2007, 10:26am

on 12/23/05 at 12:20:35, algo_wrencher wrote:

It seems whenever an array with a range of elements is given, you can always sort it in O(n) time as:

void sort(int a[])
{
for(int i=0;i<n;i++)
{
if(a[i]>a[a[i] && a[i]>i)
swap(&a[i],&a[a[i]);
}
}

This code doesn't quite look correct or I didn't get it. Can someone please elaborate. ???

Title: Re: Finding repetitions in an array (constant spac
Post by mad on Mar 3^rd, 2008, 4:11am

int x = n, y = n;
do {x = A[A[x]; y = A[y];} while (x!=y);
x = n;
do {x = A[x]; y = A[y];} while (x!=y);
return x;

Here, in the second loop, we basically start one pointer from the head node and other from point of collision. What if they don't meet? Shouldn't we work out a strategy similar to removing loops in a singly linked list?

Title: Re: Finding repetitions in an array (constant spac
Post by Grimbal on Mar 3^rd, 2008, 4:53am

They will meet.

Title: Re: Finding repetitions in an array (constant spac
Post by mad on Mar 3^rd, 2008, 5:03am

Could you explain theoretically why they will meet.
Is it because we know that the length of the list is n?

Title: Re: Finding repetitions in an array (constant spac
Post by Grimbal on Mar 3^rd, 2008, 5:17am

Suppose the first while ends after k steps. At that point, x advanced 2k steps and y did k. The advance of x is cancelled by running around the loop a number of times. So, k is a multiple of the loop length.

Then x restarts from n (the start) and both x and y advance in synchrony. As soon as x reaches the loop, it runs in circles just like y, but with y being k steps in advance. Since k is a multiple of the loop length, y must be exactly at the same place as x.

So they will meet.

Title: Re: Finding repetitions in an array (constant spac
Post by Dufus on May 8^th, 2009, 2:33am

on 02/24/04 at 23:41:54, Rezyk wrote:

I believe this works:
[hide]int x = n, y = n;
do {x = A[A[x]; y = A[y];} while (x!=y);
x = n;
do {x = A[x]; y = A[y];} while (x!=y);
return x;[/hide]

I seem to have a problem with the solution.
Consider the input as:-
5,3,4,3,1.

I tried applying the above algo to this input and it seems final output is not the desired answer.
Please help
Thanks in advance.

???

Title: Re: Finding repetitions in an array (constant spac
Post by towr on May 8^th, 2009, 3:06am

on 05/08/09 at 02:33:51, Dufus wrote:

Consider the input as:-
5,3,4,3,1.

This isn't a valid input. Input has to be an array A[1..n] populated by numbers 1..n-1; since in this case n is 5 it cannot contain a 5.

Title: Re: Finding repetitions in an array (constant spac
Post by jainshasha on May 8^th, 2009, 9:03pm

so if the sequence is 334412 then we can't find out both the repeated numbers

Title: Re: Finding repetitions in an array (constant spac
Post by Hippo on May 9^th, 2009, 1:32am

on 05/08/09 at 21:03:17, jainshasha wrote:

so if the sequence is 334412 then we can't find out both the repeated numbers

The task was to find one of the duplicated values. Not all of them.

But if the range for numbers would be 1 to n-k, you can output k duplicated numbers in O(n) time and O(1) space.

Title: Re: Finding repetitions in an array (constant spac
Post by justicezyx on May 20^th, 2009, 7:17pm

This is like the cyclic linked-list problem. The person who invented this puzzle is truly smart...

on 02/26/04 at 06:39:25, NoNothing wrote:

Title: Re: Finding repetitions in an array (constant spac
Post by computer_creator on Jun 11^th, 2009, 5:44am

on 02/29/04 at 07:57:27, towr wrote:

Well the solution still now working if you provide the array like:
int arr[10] = {8,3,6,1,7,9,1,2,4,5};
here position 9 contains 5 and position 5 contains 9.
the code stucks in a loop giving solution as 5.

Title: Re: Finding repetitions in an array (constant spac
Post by towr on Jun 11^th, 2009, 6:35am

on 06/11/09 at 05:44:33, computer_creator wrote:

Well the solution still now working if you provide the array like:
int arr[10] = {8,3,6,1,7,9,1,2,4,5};
here position 9 contains 5 and position 5 contains 9.

You're using a 0-indexed array, in which case you can't use 9. The code, as the problem, assumes you start at 1, so position 5 is 7 and position 10 is 5.

The trace of the algorithm (taking the array as starting at index 1) goes like:

int x = n, y = n;
<x = 10, y = 10>

do {x = A[A[x]; y = A[y];}
<x = 7, y = 5>
<x = 8, y = 7>
<x = 3, y = 1>
<x = 9, y = 8>
<x = 1, y = 2>
<x = 2, y = 3>
while (x!=y);
<x = 6, y = 6>

x = n;
<x = 10, y = 6>

do {x = A[x]; y = A[y];}
<x = 5, y = 9>
<x = 7, y = 4>
while (x!=y);
<x = 1, y = 1>

return x;
<x = 1>

Title: Re: Finding repetitions in an array (constant spac
Post by MUKAY on Jul 23^rd, 2010, 2:28pm

on 02/07/04 at 04:40:38, towr wrote:

if there was exactly one repetition you could find the answer by adding all the numbers and subtract n(n-1)/2

Can u elaborate this only for single repetition..with an example

Title: Re: Finding repetitions in an array (constant spac
Post by towr on Jul 23^rd, 2010, 2:33pm

on 07/23/10 at 14:28:33, MUKAY wrote:

Can u elaborate this only for single repetition..with an example

Say you have n=6, and the input 1,3,5,2,4,2
1+3+5+2+4+2=17
n(n-1)/2 = 15 (note that n(n-1)/2 = 1+2+3+..+n-1)
17-15 = 2
So 2 is the repeated number.

Title: Re: Finding repetitions in an array (constant spac
Post by MUKAY on Jul 23^rd, 2010, 2:58pm

on 07/23/10 at 14:33:07, towr wrote:

Say you have n=6, and the input 1,3,5,2,4,2
1+3+5+2+4+2=17
n(n-1)/2 = 15 (note that n(n-1)/2 = 1+2+3+..+n-1)
17-15 = 2
So 2 is the repeated number.

But this logic work only when array elements are less or equal to array size...

Title: Re: Finding repetitions in an array (constant spac
Post by towr on Jul 24^th, 2010, 2:18am

on 07/23/10 at 14:58:24, MUKAY wrote:

But this logic work only when array elements are less or equal to array size...

Yes, and that's what's given in the opening post:
"You have a read-only array A[1..n] which is populated by numbers from 1..n-1"

Title: Re: Finding repetitions in an array (constant spac
Post by HK_1984 on Apr 1^st, 2011, 5:59am

on 02/08/04 at 07:49:07, towr wrote:

Lets assume array can be modified - thus applying this solution for below array will not result in finding a duplicate in a single pass:

However in second pass of array we can know 6 is duplicate.

array : 6 1 5 4 6 2 3

step 1: 2 1 5 4 6 6 3 [replace a[1] with a [a[1]]
step 2: 1 2 5 4 6 6 3 [replace a[2] with a [a[2]]
step 3: 1 2 6 4 5 6 3
step 4: 1 2 6 4 5 6 3[replace a[4] with a [a[4]]
step 5: 1 2 6 4 5 6 3
step 6: 1 2 6 4 5 6 3[replace a[6] with a [a[6]]
step 7: 1 2 3 4 5 6 6

@ towr - please suggest.
In worsat case it mite be possible that no os passes depend upon size of array???

Title: Re: Finding repetitions in an array (constant spac
Post by Grimbal on Apr 1^st, 2011, 7:09am

In step 4 you should detect a duplicate (you have a 6 at position 3, so you check position 6, but it also has a 6).

Title: Re: Finding repetitions in an array (constant spac
Post by singhar on Jul 6^th, 2011, 10:37am

I was considering the following input:

2,5,3,7,4,9,0,1,4,6

there is a loop but it doesn't cover the entire array.. i am finding hard how this is going to work.

A[0]=2;
A[2]=3;
A[3]=7;
A[7]=1;
A[1]=5;
A[5]=9;
A[9]=6;
A[6]=0;

So we have skipped the repeating numbers 4 at positions 4 & 8.

Title: Re: Finding repetitions in an array (constant spac
Post by towr on Jul 6^th, 2011, 10:56am

That's not a valid input. If you want an array that starts at 0, then the highest number it it can be N-2 (i.e. 8 in this case); note that in the original post the array starts at index 1.

Title: Re: Finding repetitions in an array (constant spac
Post by singhar on Jul 6^th, 2011, 11:14am

Got it..

So the reason we are starting at index n is because there is no X[i] = n, so n is never part of the loop, which we are guranteed to have.

So, suppose the range is something like [1..k-1]U [k+1..n] instead of just [1..n-1] then we can start at the index k to get the same result..

Is my assumption right..?

Plus, if we are asked to detect if the array contains repeated element then the algo doesn't work, right..?

Title: Re: Finding repetitions in an array (constant spac
Post by towr on Jul 6^th, 2011, 11:37am

I'm don't understand what you mean by "starting at index n is because there is no X[i] = n", I'd always start at the front of the array, regardless of what index is the first or what number is missing.
The idea is to map every element uniquely to some place in the array and swap them to that location when you encounter them. Then if you later encounter another element with the same value and try to put it in its designated location you can spot that it's a duplicate.

Title: Re: Finding repetitions in an array (constant spac
Post by agent_purge on Jul 25^th, 2011, 12:48pm

I have another solution for this problem. It uses divide and conquer strategy. Divide array into two sub arrays using middle as pivot. Select one of sub array and recursively find repeated numbers in that sub array.

In first pass, it takes n steps, in second pass n/2, in third pass n/4 and so on.
n + n/2 + n/4 + n/8 ... + 1
= 2n
So it takes O(n) time

[hideb]

Since there are repeated numbers, by pigeonhole principle, at least one of left and right sub array will have more than one repeated numbers. Now repeat this again on sub array until you have sub array of at least 2 elements. This sub array will have repeated numbers.

start = 1
end = n

while((end - start) > 2)
{
pivot = (start+end)/2

// partiotion based on pivot
// move numbers less than pivot to left
// move numbers more than or equal to pivot to right
left = start
right = end
while(left < right)
{
while(A[left] < pivot) left++;
while(A[right] >= pivot) right--;
if(left < right)
swap(A[left], A[right]);
}

count = (end - start + 1)
less_count = (left - start)
more_count = count - less_count

expected_less_count = (pivot - start + 1)
if(less_count > expected_less_count)
{
// new range is [start, left)
end = left - 1
}
else
{
// new range is [left, end]
start = left
}
}

assert(A[start] == A[end])
return A[start]
[/hideb]

Title: Re: Finding repetitions in an array (constant spac
Post by towr on Jul 26^th, 2011, 8:08am

It's a read-only array, so you're not allowed to move the elements within the array.
(Which is also why my solution, despite garnering a lot of discussion, doesn't actually solve the problem as it's given.)

Title: Re: Finding repetitions in an array (constant spac
Post by Dufus on Dec 26^th, 2011, 2:42am

on 07/06/11 at 11:37:56, towr wrote:

I think singhar's explanation(Reply #73) gave the reasoning behind starting from the last element.. because NoNothing(Reply#25) had mentioned that we need to start from the last element so that the problem becomes similar to finding loop in a singly linked list.

Towr, I am not sure, if the same would have worked, had we started from the front of the array.

Title: Re: Finding repetitions in an array (constant spac
Post by towr on Dec 26^th, 2011, 4:06am

There were different solutions being discussed; looking back it seems Singhar may have been talking about another one then I was.