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

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

RIDDLES SITE WRITE MATH! Home Home Help Help Search Search Members Members Login Login Register Register
   wu :: forums
   riddles
   cs
(Moderators: william wu, Icarus, ThudnBlunder, Grimbal, towr, Eigenray, SMQ)
   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 22198 times)
agent_purge
Newbie
*





   


Posts: 4
Re: Finding repetitions in an array (constant spac  
« Reply #75 on: Jul 25th, 2011, 12:48pm »
Quote Quote Modify Modify

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
 
hidden:

 
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]
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 #76 on: Jul 26th, 2011, 8:08am »
Quote Quote Modify Modify

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.)
« Last Edit: Jul 26th, 2011, 8:10am by towr » IP Logged

Wikipedia, Google, Mathworld, Integer sequence DB
Dufus
Newbie
*





   


Posts: 43
Re: Finding repetitions in an array (constant spac  
« Reply #77 on: Dec 26th, 2011, 2:42am »
Quote Quote Modify Modify

on Jul 6th, 2011, 11:37am, towr wrote:
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.

 
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.
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 #78 on: Dec 26th, 2011, 4:06am »
Quote Quote Modify Modify

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

Wikipedia, Google, Mathworld, Integer sequence DB
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