Find the Duplicate Number

mediumSave

ArrayBinary SearchTwo Pointers

Given an array of integers containing n+1 elements where each element is between 1 and n (inclusive), assume there is only one duplicate number, find the duplicate one.

Note: You must not modify the array (assume the array is read-only). You must use only constant O(1) extra space and your runtime complexity should be less than O(n^2). Also, there can be multiple duplicates, but you need to return any one duplicate.

Example 1

Input

[
  1,
  3,
  4,
  2,
  2
]

Output

Explanation. The number 2 appears twice, and it's the only duplicate.

Example 2

Input

[
  3,
  1,
  3,
  4,
  2
]

Output

Explanation. The number 3 appears twice, and it's the only duplicate.

Example 3

Input

[
  1,
  1
]

Output

Explanation. The number 1 appears twice, and it's the only duplicate in a smaller array.

Example 4

Input

[
  1,
  4,
  4,
  2,
  4
]

Output

Explanation. The number 4 appears multiple times, any of these duplicates could be returned.

Follow-up: Can you design an algorithm that runs in O(n) time complexity?

Constraints:

1. The array contains only integers. 2. All integers are in the range 1 to n. 3. The array’s size is `n+1`.

Views: 3