## Finding first duplicate in array in O(n) time and O(1) space without modifying the array?

We have a array of $N$+1 integers. The integers range from 1 to $N$. The array contains at least one duplicate. Our goal is to find one of the duplicate entries. We have the constraint that we cannot modify the input array. I…