Find the Duplicate Number

You are given an array of integers. The array contains \(n+1\) integers where each integer is in the range \(1\) to \(n\) (inclusive). It is guaranteed that there is exactly one duplicate number in the list.

Your task is to identify and print the duplicate number. A popular and efficient approach to solve this problem is to use the cycle detection technique known as Floyd’s Tortoise and Hare algorithm.

inputFormat

A single line of input is given, containing space-separated integers representing the list. It is guaranteed that there is exactly one duplicated number in the list.

outputFormat

Print the duplicate number to standard output.## sample

1 3 4 2 2

2