Author |
Topic: Finding repetitions in an array (constant space) (Read 22166 times) |
|
noname
Guest
|
 |
Re: Finding repetitions in an array (constant spac
« Reply #50 on: Dec 18th, 2005, 2:54am » |
 Quote  Modify
 Remove
|
on Sep 27th, 2004, 12:22pm, John_Gaughan wrote:| 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 |
|
|
|
noname
Guest
|
|
Re: Finding repetitions in an array (constant spac
« Reply #51 on: Dec 18th, 2005, 2:56am » |
Quote Modify
Remove
|
Do you know what linear time means??
on Feb 7th, 2004, 11:41pm, John_Gaughan wrote: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? |
|
|
|
IP Logged |
|
|
|
algo_wrencher
Newbie
I am not insane, I enjoy every moment of it!
Posts: 44
|
|
Re: Finding repetitions in an array (constant spac
« Reply #52 on: Dec 23rd, 2005, 12:20pm » |
Quote Modify
|
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... 
|
|
IP Logged |
|
|
|
KC
Newbie
\m/ what's a metalhead doing solving puzzles?! \m/
Gender: 
Posts: 3
|
|
Re: Finding repetitions in an array (constant spac
« Reply #53 on: Apr 27th, 2007, 10:26am » |
Quote Modify
|
on Dec 23rd, 2005, 12:20pm, 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. 
|
|
IP Logged |
|
|
|
mad
Junior Member
Posts: 118
|
|
Re: Finding repetitions in an array (constant spac
« Reply #54 on: Mar 3rd, 2008, 4:11am » |
Quote Modify
|
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?
|
|
IP Logged |
|
|
|
Grimbal
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 7527
|
|
Re: Finding repetitions in an array (constant spac
« Reply #55 on: Mar 3rd, 2008, 4:53am » |
Quote Modify
|
They will meet.
|
|
IP Logged |
|
|
|
mad
Junior Member
Posts: 118
|
|
Re: Finding repetitions in an array (constant spac
« Reply #56 on: Mar 3rd, 2008, 5:03am » |
Quote Modify
|
Could you explain theoretically why they will meet.
Is it because we know that the length of the list is n?
|
|
IP Logged |
|
|
|
Grimbal
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 7527
|
|
Re: Finding repetitions in an array (constant spac
« Reply #57 on: Mar 3rd, 2008, 5:17am » |
Quote Modify
|
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.
|
|
IP Logged |
|
|
|
Dufus
Newbie
Posts: 43
|
|
Re: Finding repetitions in an array (constant spac
« Reply #58 on: May 8th, 2009, 2:33am » |
Quote Modify
|
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; |
|
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.
|
| « Last Edit: May 8th, 2009, 2:34am by Dufus » |
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 #59 on: May 8th, 2009, 3:06am » |
Quote Modify
|
on May 8th, 2009, 2:33am, 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.
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
jainshasha
Newbie
Posts: 14
|
|
Re: Finding repetitions in an array (constant spac
« Reply #60 on: May 8th, 2009, 9:03pm » |
Quote Modify
|
so if the sequence is 334412 then we can't find out both the repeated numbers
|
|
IP Logged |
|
|
|
Hippo
Uberpuzzler
Gender:
Posts: 919
|
|
Re: Finding repetitions in an array (constant spac
« Reply #61 on: May 9th, 2009, 1:32am » |
Quote Modify
|
on May 8th, 2009, 9:03pm, 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.
|
| « Last Edit: May 9th, 2009, 1:33am by Hippo » |
IP Logged |
|
|
|
justicezyx
Newbie
Posts: 2
|
|
Re: Finding repetitions in an array (constant spac
« Reply #62 on: May 20th, 2009, 7:17pm » |
Quote Modify
|
This is like the cyclic linked-list problem. The person who invented this puzzle is truly smart...
on Feb 26th, 2004, 6:39am, NoNothing wrote:
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 |
|
|
|
computer_creator
Newbie
Posts: 2
|
|
Re: Finding repetitions in an array (constant spac
« Reply #63 on: Jun 11th, 2009, 5:44am » |
Quote Modify
|
on Feb 29th, 2004, 7:57am, towr wrote:
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.. |
|
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.
|
|
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 #64 on: Jun 11th, 2009, 6:35am » |
Quote Modify
|
on Jun 11th, 2009, 5:44am, 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>
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
MUKAY
Newbie
Posts: 3
|
|
Re: Finding repetitions in an array (constant spac
« Reply #65 on: Jul 23rd, 2010, 2:28pm » |
Quote Modify
|
on Feb 7th, 2004, 4:40am, 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
|
|
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 #66 on: Jul 23rd, 2010, 2:33pm » |
Quote Modify
|
on Jul 23rd, 2010, 2:28pm, 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.
|
| « Last Edit: Jul 23rd, 2010, 2:33pm by towr » |
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
MUKAY
Newbie
Posts: 3
|
|
Re: Finding repetitions in an array (constant spac
« Reply #67 on: Jul 23rd, 2010, 2:58pm » |
Quote Modify
|
on Jul 23rd, 2010, 2:33pm, 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...
|
|
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 #68 on: Jul 24th, 2010, 2:18am » |
Quote Modify
|
on Jul 23rd, 2010, 2:58pm, 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"
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
HK_1984
Newbie
Posts: 1
|
|
Re: Finding repetitions in an array (constant spac
« Reply #69 on: Apr 1st, 2011, 5:59am » |
Quote Modify
|
on Feb 8th, 2004, 7:49am, towr wrote:::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):: |
|
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
|
|
IP Logged |
|
|
|
Grimbal
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 7527
|
|
Re: Finding repetitions in an array (constant spac
« Reply #70 on: Apr 1st, 2011, 7:09am » |
Quote Modify
|
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).
|
|
IP Logged |
|
|
|
singhar
Newbie
Posts: 22
|
|
Re: Finding repetitions in an array (constant spac
« Reply #71 on: Jul 6th, 2011, 10:37am » |
Quote Modify
|
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.
|
|
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 #72 on: Jul 6th, 2011, 10:56am » |
Quote Modify
|
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.
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
singhar
Newbie
Posts: 22
|
|
Re: Finding repetitions in an array (constant spac
« Reply #73 on: Jul 6th, 2011, 11:14am » |
Quote Modify
|
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..?
|
|
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 #74 on: Jul 6th, 2011, 11:37am » |
Quote Modify
|
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.
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print