Author |
Topic: Finding repetitions in an array (constant space) (Read 22167 times) |
|
agent_purge
Newbie
Posts: 4
|
 |
Re: Finding repetitions in an array (constant spac
« Reply #75 on: Jul 25th, 2011, 12:48pm » |
 Quote  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: 
Posts: 13730
|
|
Re: Finding repetitions in an array (constant spac
« Reply #76 on: Jul 26th, 2011, 8:08am » |
Quote 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 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:
Posts: 13730
|
|
Re: Finding repetitions in an array (constant spac
« Reply #78 on: Dec 26th, 2011, 4:06am » |
Quote 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
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print