Given a vectors of size $n$ with integer data within $[1, n-1]$ range, find $if$ and $which$ numbers are multiple duplicates (numbers appearing more than once). The time complexity ought to be linear and space complexity constant (don't use any auxiliary data structure except the input vector and variables) and the input data set ought not to be modified.
I'm trying to solve this problem for at least one multiple duplicate (as a starting point, although I don't know if the solution to this case can be expanded to the general case of at least two multiple duplicates). Here's what I've done so far:
The $if$ part is relatively easy, taken we can be proven using the pigeonhole principle to show that there $will$ be at least a simple duplicate within the given data set.
The $which$ part, on the other hand, is what gives me headaches. Unlike the missing number problem, we cannot simply Xor the numbers. Neither can we sum them up and subtract the sum from 1 to n-1, thus finding a simple duplicate. Can anyone suggest a good approach towards this problem? You are not allowed to modify the input array.