Detect the Only Duplicate in a List

You are given a list nums of length n + 1 picked from the range 1, 2, ..., n. By the pigeonhole principle, there must be a duplicate. Find and return it. There is guaranteed to be exactly one duplicate.

Bonus: Can you do this in \(\mathcal{O}(n)$` time and `$\mathcal{O}(1)\) space?

Constraints

• n ≤ 10,000

https://binarysearch.com/problems/Detect-the-Only-Duplicate-in-a-List

Examples

Example 1

Input

• nums = [1, 2, 3, 1]

Output

• answer = 1

Example 2

Input

• nums = [4, 2, 1, 3, 2]

Output

• answer = 2

Solution