wu :: forums
« wu :: forums - Finding repetitions in an array (constant space) »

Welcome, Guest. Please Login or Register.
Oct 31st, 2024, 4:33pm

RIDDLES SITE WRITE MATH! Home Home Help Help Search Search Members Members Login Login Register Register
   wu :: forums
   riddles
   cs
(Moderators: william wu, towr, SMQ, Grimbal, Icarus, ThudnBlunder, Eigenray)
   Finding repetitions in an array (constant space)
« Previous topic | Next topic »
Pages: 1 2 3  4 Reply Reply Notify of replies Notify of replies Send Topic Send Topic Print Print
   Author  Topic: Finding repetitions in an array (constant space)  (Read 22197 times)
tseuG
Junior Member
**





   


Gender: male
Posts: 62
Finding repetitions in an array (constant space)  
« on: Feb 6th, 2004, 12:11pm »
Quote Quote Modify 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!

5187759 5187759   john23874   SnowmanJTG
WWW Email

Gender: male
Posts: 767
Re: Finding repetitions in an array (constant spac  
« Reply #1 on: Feb 6th, 2004, 12:19pm »
Quote Quote Modify 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: male
Posts: 62
Re: Finding repetitions in an array (constant spac  
« Reply #2 on: Feb 6th, 2004, 4:51pm »
Quote Quote Modify Modify

No.
IP Logged
towr
wu::riddles Moderator
Uberpuzzler
*****



Some people are average, some are just mean.

   


Gender: male
Posts: 13730
Re: Finding repetitions in an array (constant spac  
« Reply #3 on: Feb 7th, 2004, 4:40am »
Quote Quote Modify 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: male
Posts: 62
Re: Finding repetitions in an array (constant spac  
« Reply #4 on: Feb 7th, 2004, 8:32am »
Quote Quote Modify 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!

5187759 5187759   john23874   SnowmanJTG
WWW Email

Gender: male
Posts: 767
Re: Finding repetitions in an array (constant spac  
« Reply #5 on: Feb 7th, 2004, 11:41pm »
Quote Quote Modify 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: male
Posts: 62
Re: Finding repetitions in an array (constant spac  
« Reply #6 on: Feb 8th, 2004, 7:10am »
Quote Quote Modify 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: male
Posts: 13730
Re: Finding repetitions in an array (constant spac  
« Reply #7 on: Feb 8th, 2004, 7:49am »
Quote Quote Modify 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: male
Posts: 19
Re: Finding repetitions in an array (constant spac  
« Reply #8 on: Feb 8th, 2004, 8:29am »
Quote Quote Modify Modify

Are we allowed to change A ?
IP Logged
tseuG
Junior Member
**





   


Gender: male
Posts: 62
Re: Finding repetitions in an array (constant spac  
« Reply #9 on: Feb 8th, 2004, 9:02am »
Quote Quote Modify 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: male
Posts: 13730
Re: Finding repetitions in an array (constant spac  
« Reply #10 on: Feb 8th, 2004, 10:05am »
Quote Quote Modify 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: male
Posts: 13730
Re: Finding repetitions in an array (constant spac  
« Reply #11 on: Feb 8th, 2004, 10:41am »
Quote Quote Modify 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.. Tongue
« 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!

5187759 5187759   john23874   SnowmanJTG
WWW Email

Gender: male
Posts: 767
Re: Finding repetitions in an array (constant spac  
« Reply #12 on: Feb 8th, 2004, 6:20pm »
Quote Quote Modify 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 Wink
IP Logged

x = (0x2B | ~0x2B)
x == the_question
Barukh
Uberpuzzler
*****






   


Gender: male
Posts: 2276
Re: Finding repetitions in an array (constant spac  
« Reply #13 on: Feb 9th, 2004, 5:56am »
Quote Quote Modify Modify

That's a great puzzle! All my friends to whom I presented it, are blowing their brains  Grin
 
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: male
Posts: 2276
Re: Finding repetitions in an array (constant spac  
« Reply #14 on: Feb 9th, 2004, 5:58am »
Quote Quote Modify 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.. Tongue

I don't think this product fits the constant space requirement either...  Wink
« Last Edit: Feb 9th, 2004, 5:58am by Barukh » IP Logged
tseuG
Junior Member
**





   


Gender: male
Posts: 62
Re: Finding repetitions in an array (constant spac  
« Reply #15 on: Feb 9th, 2004, 6:02am »
Quote Quote Modify Modify

   Barukh, it's a read-only array.
IP Logged
towr
wu::riddles Moderator
Uberpuzzler
*****



Some people are average, some are just mean.

   


Gender: male
Posts: 13730
Re: Finding repetitions in an array (constant spac  
« Reply #16 on: Feb 9th, 2004, 6:31am »
Quote Quote Modify Modify

on Feb 9th, 2004, 5:58am, Barukh wrote:
I don't think this product fits the constant space requirement either...  Wink
meh, unlimited space seems constant enough Tongue
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: male
Posts: 2276
Re: Finding repetitions in an array (constant spac  
« Reply #17 on: Feb 10th, 2004, 6:12am »
Quote Quote Modify 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...  Shocked
IP Logged
Corleone
Newbie
*





   


Posts: 3
Re: Finding repetitions in an array (constant spac  
« Reply #18 on: Feb 15th, 2004, 12:59pm »
Quote Quote Modify 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!

5187759 5187759   john23874   SnowmanJTG
WWW Email

Gender: male
Posts: 767
Re: Finding repetitions in an array (constant spac  
« Reply #19 on: Feb 15th, 2004, 3:29pm »
Quote Quote Modify 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

Email

Re: Finding repetitions in an array (constant spac  
« Reply #20 on: Feb 23rd, 2004, 9:40am »
Quote Quote Modify Modify Remove 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

Email

Re: Finding repetitions in an array (constant spac  
« Reply #21 on: Feb 23rd, 2004, 3:10pm »
Quote Quote Modify Modify Remove 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
**





   
Email

Gender: male
Posts: 85
Re: Finding repetitions in an array (constant spac  
« Reply #22 on: Feb 24th, 2004, 11:41pm »
Quote Quote Modify 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

Email

Re: Finding repetitions in an array (constant spac  
« Reply #23 on: Feb 25th, 2004, 6:06am »
Quote Quote Modify Modify Remove 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 Smiley
IP Logged
Barukh
Uberpuzzler
*****






   


Gender: male
Posts: 2276
Re: Finding repetitions in an array (constant spac  
« Reply #24 on: Feb 26th, 2004, 1:13am »
Quote Quote Modify Modify

Brilliant!!! Bravo, Rezyk and NoNothing (who claims to be the inventor of the code  Grin)!
 
By the way, can you prove that the code is correct? It's not obvious... I believe I've got a demonstration.
IP Logged
Pages: 1 2 3  4 Reply Reply Notify of replies Notify of replies Send Topic Send Topic Print Print

« Previous topic | Next topic »

Powered by YaBB 1 Gold - SP 1.4!
Forum software copyright © 2000-2004 Yet another Bulletin Board