# Find a repeated element in linear time

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

• Does this answer your question? Finding duplicate in immutable array in linear time and constant space May 22 at 17:50
• @Nathaniel sorry, I should have stated that the divide and conquer approach was mandatory May 22 at 18:15
• Then you should edit your post to add this requirement. May 22 at 18:16

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.
• Going to accept this as an aswer, because it is the right idea. However, check ${1,1,2,3,3}$ May 22 at 19:50
• @Norhther depending on the half you put $2$ in, the larger one will alway contain a duplicate, so that case is not a problem. May 22 at 20:33
• I was aiming for something more like $1,2,3$, here both halfs have 1 element May 22 at 20:34
• @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) May 22 at 20:35