ProAnswers.org

How to find duplicate integer in an array

An array of length n+1 is populated with integers in the range [1, n]. How to find a duplicate integer in linear time with O(1) space. The array is read-only and may not be modified.

Compute the sum S as sum of all integers from 1 to n+1 i.e 1+2+3+…+n+1
Compute the sum S1 as sum of all integers in the array
Compute d=S-S1
Then the duplicate integer will be (n+1)-d