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