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