Find Duplicate in Array

Given a read only array of n + 1 integers between 1 and n, find one number that repeats in linear time using less than O(n) space and traversing the stream sequentially O(1) times.

Sample Input:

[3 4 1 4 1]

Sample Output:

1

If there are multiple possible answers ( like in the sample case above ), output any one.

If there is no duplicate, output -1

Interview Code Editor
Hints
  • Hint 1
  • Solution Approach
  • Complete Solution
7247 successful submissions.
Asked In:
  • Amazon
  • VMWare
  • Riverbed
Click here to jump start your coding interview preparation