Find Duplicate in Array

Problem Description

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.

If there are multiple possible answers ( like in the sample case ), output any one, if there is no duplicate, output -1

Problem Constraints

1 <= |A| <= 10⁵
1 <= A_i <= |A|

Input Format

The first argument is an integer array A.

Output Format

Return the integer that repeats in array A

Example Input

Input 1:

A = [3, 4, 1, 4, 2]

Input 2:

A = [1, 2, 3]

Input 3:

A = [3, 4, 1, 4, 1]

Example Output

Output 1:

Output 2:

-1

Output 3:

Example Explanation

Explanation 1:

4 repeats itself in the array [3, 4, 1, 4, 2]

Explanation 2:

No number repeats itself in the array [1, 2, 3]

Explanation 3:

1 and 4 repeats itself in the array [3, 4, 1, 4, 1], we can return 1 or 4

NOTE: You only need to implement the given function. Do not read input, instead use the arguments to the function. Do not print the output, instead return values as specified. Still have a question? Checkout Sample Codes for more details.

Start solving Find Duplicate in Array on Interview Code Editor

Hints

Hint 1
Solution Approach
Complete Solution

Asked In:

Find Duplicate in Array

Discussion