Find the Duplicate Number

Medium

Description

A train coach has seats numbered 1 to n. The railway gives out n + 1 tickets, so some seat number must be given out more than once.

The array nums holds the seat number written on each ticket. Exactly one seat number is repeated. Every other seat number appears at most once. The repeated number can appear two times or more.

Return the repeated seat number.

Rules: do not change the array, and use only a constant amount of extra space.

Examples

Example 1:

Input: nums = [2,4,1,3,3]
Output: 3
Explanation: Seat 3 is on two tickets. Every other seat appears once.

Example 2:

Input: nums = [5,2,3,5,1,4]
Output: 5
Explanation: Seat 5 is on two tickets.

Example 3:

Input: nums = [2,2,2,2,2]
Output: 2
Explanation: All five tickets show seat 2. A repeated number can appear many times.

Array
Two Pointers
Binary Search
Bit Manipulation
Floyd's Cycle Finding

Constraints

1 <= n <= 10^5
nums.length == n + 1
1 <= nums[i] <= n
Exactly one number is repeated, and it appears two or more times. Every other number appears at most once.

Examples

3 shown

Example 1

Input

[2,4,1,3,3]

Output

Example 2

Input

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

Output

Example 3

Input

[2,2,2,2,2]

Output

Opening the editor...