Find Duplicate in Array

ArrayHash Table

Given an array of integers where each integer is between 1 and n (inclusive), where 'n' is the length of the array, write a function that finds and returns the integer that appears more than once in the array. Assume there is exactly one integer that meets this condition.

Example 1

Input

[
  3,
  1,
  3,
  4,
  2
]

Output

Explanation. The number 3 appears twice in the array.

Example 2

Input

[
  1,
  2,
  2,
  3,
  4
]

Output

Explanation. The number 2 appears twice in the array.

Example 3

Input

[
  1,
  1
]

Output

Explanation. The number 1 appears twice in the array, which are the only two numbers present.

Example 4

Input

[
  5,
  4,
  3,
  2,
  5,
  1
]

Output

Explanation. The number 5 appears twice in the array.

Follow-up: Can you implement your solution in O(n) time complexity and O(1) space complexity by modifying the input array?

Constraints:

The input array will have a length of at least 2 and at most 10,000. Each integer in the array is in the range from 1 to n, where n is the size of the array.

Views: 2