Author |
Topic: Finding repetitions in an array (constant space) (Read 22169 times) |
|
NoNothing
Guest
|
 |
Re: Finding repetitions in an array (constant spac
« Reply #25 on: Feb 26th, 2004, 6:39am » |
 Quote  Modify
 Remove
|
on Feb 26th, 2004, 1:13am, Barukh wrote:Brilliant!!! Bravo, Rezyk and NoNothing (who claims to be the inventor of the code  )!
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.
|
|
 IP Logged |
|
|
|
dont_get_it
Guest
|
|
Re: Finding repetitions in an array (constant spac
« Reply #26 on: Feb 29th, 2004, 7:31am » |
Quote Modify
Remove
|
on Feb 24th, 2004, 11:41pm, Rezyk wrote: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; |
|
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
|
|
IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender: 
Posts: 13730
|
|
Re: Finding repetitions in an array (constant spac
« Reply #27 on: Feb 29th, 2004, 7:57am » |
Quote Modify
|
Quote:
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..
|
| « Last Edit: Feb 29th, 2004, 7:58am by towr » |
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
berry
Guest
|
|
Re: Finding repetitions in an array (constant spac
« Reply #28 on: Mar 11th, 2004, 12:11pm » |
Quote Modify
Remove
|
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
|
|
IP Logged |
|
|
|
lovey
Newbie
Posts: 6
|
|
Re: Finding repetitions in an array (constant spac
« Reply #29 on: Mar 12th, 2004, 7:12pm » |
Quote Modify
|
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. 
|
|
IP Logged |
|
|
|
Barukh
Uberpuzzler
Gender:
Posts: 2276
|
|
Re: Finding repetitions in an array (constant spac
« Reply #30 on: Mar 13th, 2004, 4:45am » |
Quote Modify
|
on Mar 11th, 2004, 12:11pm, 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 towrs reply #3 in this thread.
on Mar 12th, 2004, 7:12pm, 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 dont see how this approach solves the problem in general.
|
|
IP Logged |
|
|
|
lovey
Newbie
Posts: 6
|
|
Re: Finding repetitions in an array (constant spac
« Reply #31 on: Mar 13th, 2004, 9:37am » |
Quote Modify
|
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.
|
|
IP Logged |
|
|
|
Rezyk
Junior Member
Gender:
Posts: 85
|
|
Re: Finding repetitions in an array (constant spac
« Reply #32 on: Mar 13th, 2004, 4:05pm » |
Quote Modify
|
What happens with 2 1 5 5 4?
|
|
IP Logged |
|
|
|
lovey
Newbie
Posts: 6
|
|
Re: Finding repetitions in an array (constant spac
« Reply #33 on: Mar 13th, 2004, 4:46pm » |
Quote Modify
|
on Mar 13th, 2004, 4:05pm, 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.
|
|
IP Logged |
|
|
|
Rezyk
Junior Member
Gender:
Posts: 85
|
|
Re: Finding repetitions in an array (constant spac
« Reply #34 on: Mar 13th, 2004, 9:37pm » |
Quote Modify
|
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?
|
| « Last Edit: Mar 13th, 2004, 9:39pm by Rezyk » |
IP Logged |
|
|
|
lovey
Newbie
Posts: 6
|
|
Re: Finding repetitions in an array (constant spac
« Reply #35 on: Mar 14th, 2004, 9:44am » |
Quote Modify
|
on Mar 13th, 2004, 9:37pm, 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. ?
|
| « Last Edit: Mar 14th, 2004, 9:51am by lovey » |
IP Logged |
|
|
|
Neelesh
Guest
|
|
Re: Finding repetitions in an array (constant spac
« Reply #36 on: Sep 17th, 2004, 12:30am » |
Quote Modify
Remove
|
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].
|
|
IP Logged |
|
|
|
Neelesh Maurya
Guest
|
|
Re: Finding repetitions in an array (constant spac
« Reply #37 on: Sep 20th, 2004, 10:51pm » |
Quote Modify
Remove
|
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;
}
|
|
IP Logged |
|
|
|
Barukh
Uberpuzzler
Gender:
Posts: 2276
|
|
Re: Finding repetitions in an array (constant spac
« Reply #38 on: Sep 22nd, 2004, 5:57am » |
Quote Modify
|
on Sep 17th, 2004, 12:30am, 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...
|
|
IP Logged |
|
|
|
sujansunil
Newbie
Posts: 1
|
 |
Re: Finding repetitions in an array (constant spac
« Reply #39 on: Sep 27th, 2004, 9:43am » |
Quote Modify
|
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.
|
|
IP Logged |
|
|
|
John_Gaughan
Uberpuzzler
Behold, the power of cheese!
    
Gender:
Posts: 767
|
|
Re: Finding repetitions in an array (constant spac
« Reply #40 on: Sep 27th, 2004, 12:22pm » |
Quote Modify
|
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.
|
|
IP Logged |
x = (0x2B | ~0x2B)
x == the_question
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Finding repetitions in an array (constant spac
« Reply #41 on: Sep 27th, 2004, 1:13pm » |
Quote Modify
|
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.
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
Vincent Lascaux
Guest
|
|
Re: Finding repetitions in an array (constant spac
« Reply #42 on: Nov 23rd, 2004, 9:36am » |
Quote Modify
Remove
|
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.
|
|
IP Logged |
|
|
|
Vincent Lascaux
Guest
|
|
Re: Finding repetitions in an array (constant spac
« Reply #43 on: Nov 23rd, 2004, 9:41am » |
Quote Modify
Remove
|
on Nov 23rd, 2004, 9:36am, 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:)
|
|
IP Logged |
|
|
|
puzzlecracker
Senior Riddler
Men have become the tools of their tools
Gender:
Posts: 319
|
|
Re: Finding repetitions in an array (constant spac
« Reply #44 on: Dec 8th, 2004, 6:20pm » |
Quote Modify
|
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;
|
|
IP Logged |
While we are postponing, life speeds by
|
|
|
cssomnath
Newbie
Posts: 20
|
|
Re: Finding repetitions in an array (constant spac
« Reply #45 on: Dec 12th, 2004, 6:07am » |
Quote Modify
|
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
|
| « Last Edit: Dec 12th, 2004, 6:15am by cssomnath » |
IP Logged |
|
|
|
Joe
Guest
|
|
Re: Finding repetitions in an array (constant spac
« Reply #46 on: Dec 13th, 2004, 8:56am » |
Quote Modify
Remove
|
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!
|
|
IP Logged |
|
|
|
puzzlecracker
Senior Riddler
Men have become the tools of their tools
Gender:
Posts: 319
|
|
Re: Finding repetitions in an array (constant spac
« Reply #47 on: Dec 13th, 2004, 9:13am » |
Quote Modify
|
Joe - this is trivial problem you've just described.
|
|
IP Logged |
While we are postponing, life speeds by
|
|
|
puzzlecracker
Senior Riddler
Men have become the tools of their tools
Gender:
Posts: 319
|
|
Re: Finding repetitions in an array (constant spac
« Reply #48 on: Dec 16th, 2004, 10:24pm » |
Quote Modify
|
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; |
|
|
| « Last Edit: Dec 16th, 2004, 10:28pm by puzzlecracker » |
IP Logged |
While we are postponing, life speeds by
|
|
|
Grimbal
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 7527
|
|
Re: Finding repetitions in an array (constant spac
« Reply #49 on: Dec 17th, 2004, 12:47am » |
Quote Modify
|
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.
|
|
IP Logged |
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print