Author |
Topic: Finding repetitions in an array (constant space) (Read 22219 times) |
|
tseuG
Junior Member
Gender: 
Posts: 62
|
 |
Finding repetitions in an array (constant space)
« on: Feb 6th, 2004, 12:11pm » |
 Quote  Modify
|
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.
|
| « Last Edit: Feb 9th, 2004, 6:02am by tseuG » |
 IP Logged |
|
|
|
John_Gaughan
Uberpuzzler
Behold, the power of cheese!
    
 
Gender:
Posts: 767
|
|
Re: Finding repetitions in an array (constant spac
« Reply #1 on: Feb 6th, 2004, 12:19pm » |
Quote Modify
|
Is the array sorted, such that ai >= ai-1?
|
| « Last Edit: Feb 6th, 2004, 12:20pm by John_Gaughan » |
IP Logged |
x = (0x2B | ~0x2B)
x == the_question
|
|
|
tseuG
Junior Member
Gender:
Posts: 62
|
|
Re: Finding repetitions in an array (constant spac
« Reply #2 on: Feb 6th, 2004, 4:51pm » |
Quote Modify
|
No.
|
|
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 #3 on: Feb 7th, 2004, 4:40am » |
Quote Modify
|
if there was exactly one repetition you could find the answer by adding all the numbers and subtract n(n-1)/2
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
tseuG
Junior Member
Gender:
Posts: 62
|
|
Re: Finding repetitions in an array (constant spac
« Reply #4 on: Feb 7th, 2004, 8:32am » |
Quote Modify
|
Yes. However, in this case, the repetitions can be more than one (and there has to be atleast one).
|
|
IP Logged |
|
|
|
John_Gaughan
Uberpuzzler
Behold, the power of cheese!
Gender:
Posts: 767
|
|
Re: Finding repetitions in an array (constant spac
« Reply #5 on: Feb 7th, 2004, 11:41pm » |
Quote Modify
|
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 |
x = (0x2B | ~0x2B)
x == the_question
|
|
|
tseuG
Junior Member
Gender:
Posts: 62
|
|
Re: Finding repetitions in an array (constant spac
« Reply #6 on: Feb 8th, 2004, 7:10am » |
Quote Modify
|
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).
|
|
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 #7 on: Feb 8th, 2004, 7:49am » |
Quote Modify
|
::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)::
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
DH
Newbie
Gender:
Posts: 19
|
|
Re: Finding repetitions in an array (constant spac
« Reply #8 on: Feb 8th, 2004, 8:29am » |
Quote Modify
|
Are we allowed to change A ?
|
|
IP Logged |
|
|
|
tseuG
Junior Member
Gender:
Posts: 62
|
|
Re: Finding repetitions in an array (constant spac
« Reply #9 on: Feb 8th, 2004, 9:02am » |
Quote Modify
|
towr, could you explain your solution in more detail? How is the final condition a[m] = m and a[k] = m (k!=m) 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.
|
| « Last Edit: Feb 8th, 2004, 9:03am by tseuG » |
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 #10 on: Feb 8th, 2004, 10:05am » |
Quote Modify
|
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.
|
| « Last Edit: Feb 8th, 2004, 10:07am by towr » |
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
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 #11 on: Feb 8th, 2004, 10:41am » |
Quote Modify
|
Here's another nice but tricky solution..
Take the product of (the first) n primes, [prod]i=1nprimei, and then for i from 1 to n divide by primea[i] until this doesn't yield an integer..
The tricky part is justifying where you get those n primes.. 
|
| « Last Edit: Feb 8th, 2004, 10:45am by towr » |
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
John_Gaughan
Uberpuzzler
Behold, the power of cheese!
Gender:
Posts: 767
|
|
Re: Finding repetitions in an array (constant spac
« Reply #12 on: Feb 8th, 2004, 6:20pm » |
Quote Modify
|
on Feb 8th, 2004, 7:10am, 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 
|
|
IP Logged |
x = (0x2B | ~0x2B)
x == the_question
|
|
|
Barukh
Uberpuzzler
Gender:
Posts: 2276
|
|
Re: Finding repetitions in an array (constant spac
« Reply #13 on: Feb 9th, 2004, 5:56am » |
Quote Modify
|
That's a great puzzle! All my friends to whom I presented it, are blowing their brains 
on Feb 8th, 2004, 9:02am, 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)?
|
|
IP Logged |
|
|
|
Barukh
Uberpuzzler
Gender:
Posts: 2276
|
|
Re: Finding repetitions in an array (constant spac
« Reply #14 on: Feb 9th, 2004, 5:58am » |
Quote Modify
|
on Feb 8th, 2004, 10:41am, towr wrote:Here's another nice but tricky solution..
Take the product of (the first) n primes, [prod]i=1nprimei, and then for i from 1 to n divide by primea[i] until this doesn't yield an integer..
The tricky part is justifying where you get those n primes.. |
|
I don't think this product fits the constant space requirement either...
|
| « Last Edit: Feb 9th, 2004, 5:58am by Barukh » |
IP Logged |
|
|
|
tseuG
Junior Member
Gender:
Posts: 62
|
|
Re: Finding repetitions in an array (constant spac
« Reply #15 on: Feb 9th, 2004, 6:02am » |
Quote Modify
|
Barukh, it's a read-only array.
|
|
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 #16 on: Feb 9th, 2004, 6:31am » |
Quote Modify
|
on Feb 9th, 2004, 5:58am, Barukh wrote:| I don't think this product fits the constant space requirement either... |
|
meh, unlimited space seems constant enough
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..
|
| « Last Edit: Feb 9th, 2004, 6:35am by towr » |
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
Barukh
Uberpuzzler
Gender:
Posts: 2276
|
|
Re: Finding repetitions in an array (constant spac
« Reply #17 on: Feb 10th, 2004, 6:12am » |
Quote Modify
|
on Feb 9th, 2004, 6:02am, tseuG wrote:| Barukh, it's a read-only array. |
|
Well, it seems at this point I will ask for a hint... 
|
|
IP Logged |
|
|
|
Corleone
Newbie
Posts: 3
|
|
Re: Finding repetitions in an array (constant spac
« Reply #18 on: Feb 15th, 2004, 12:59pm » |
Quote Modify
|
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.
::
|
|
IP Logged |
|
|
|
John_Gaughan
Uberpuzzler
Behold, the power of cheese!
Gender:
Posts: 767
|
|
Re: Finding repetitions in an array (constant spac
« Reply #19 on: Feb 15th, 2004, 3:29pm » |
Quote Modify
|
on Feb 15th, 2004, 12:59pm, 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.
|
|
IP Logged |
x = (0x2B | ~0x2B)
x == the_question
|
|
|
NoNothing
Guest
|
|
Re: Finding repetitions in an array (constant spac
« Reply #20 on: Feb 23rd, 2004, 9:40am » |
Quote Modify
 Remove
|
Tseug, thanks for this nice problem. And thanks for not hasting to post a solution. Here's a hint for those who want it:
::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.::
|
|
IP Logged |
|
|
|
lovey
Guest
|
|
Re: Finding repetitions in an array (constant spac
« Reply #21 on: Feb 23rd, 2004, 3:10pm » |
Quote Modify
Remove
|
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 ?
|
|
IP Logged |
|
|
|
Rezyk
Junior Member
Gender:
Posts: 85
|
|
Re: Finding repetitions in an array (constant spac
« Reply #22 on: Feb 24th, 2004, 11:41pm » |
Quote Modify
|
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 |
|
|
|
NoNothing
Guest
|
|
Re: Finding repetitions in an array (constant spac
« Reply #23 on: Feb 25th, 2004, 6:06am » |
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; |
|
Oh, no, you stole my code for super_linear_time_const_space_find_rep_alg()! Damn those opensource advocates.
Well, almost 
|
|
IP Logged |
|
|
|
Barukh
Uberpuzzler
Gender:
Posts: 2276
|
|
Re: Finding repetitions in an array (constant spac
« Reply #24 on: Feb 26th, 2004, 1:13am » |
Quote Modify
|
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.
|
|
IP Logged |
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print