0
$\begingroup$

Given an array of $n$ elements, containing values in the range $[1, n-1] $ (assume $ n > 1 $) this implies there is at least one repeated element. The problem is to get one of the repeated values in linear time on average.

My first try was to do something with the Partition scheme from Quicksort. However, I don't know how to address the following problem:

  • We can divide the problem selecting a pivot, and then for each value $ <= $ than the pivot, we know that they will be in the range $0..n/2 - 1$, and the following values $>$ than the pivot, they will be in $n/2 + 1..n$.

I can't check both of those partitions, because the cost would be $O(n\log n)$ per Master Theorem.

The only way I think I can do it is only checking left or right, however, i.e., if the repeated element was in the left and I check the right, is going to be somewhat the same.

So my intuition is telling me that maybe, if I check first the left part for this condition, and after that, the right one in some recursive manner, this is going to give me a linear algorithm on average. Am I right or is there any better way to do it?

Edit: the divide and conquer approach is mandatory

$\endgroup$
3
1
$\begingroup$

If you choose $\frac{n}{2}$ as the pivot to do the partition, you just need then to continue the search in the half containing strictly more than $\frac{n}{2}$ elements.

That way you don't have to check both halves.

$\endgroup$
6
  • $\begingroup$ Going to accept this as an aswer, because it is the right idea. However, check $ {1,1,2,3,3} $ $\endgroup$
    – Norhther
    May 22 at 19:50
  • $\begingroup$ @Norhther depending on the half you put $2$ in, the larger one will alway contain a duplicate, so that case is not a problem. $\endgroup$
    – Nathaniel
    May 22 at 20:33
  • $\begingroup$ I was aiming for something more like $1,2,3$, here both halfs have 1 element $\endgroup$
    – Norhther
    May 22 at 20:34
  • $\begingroup$ @Norhther Again, in this example, you have to put $2$ in one of the halves, you cannot make it disappear. (And this example does not contain duplicates) $\endgroup$
    – Nathaniel
    May 22 at 20:35
  • $\begingroup$ How's that? I thought the algorithm would be check if the pivot is the duplicate in the half with more elements, and if not, check that half. $\endgroup$
    – Norhther
    May 22 at 20:37

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.