# Find the Duplicate Number

**1. Clarify the problem:**
Before diving into solving the problem, let's clarify the requirements:

- We are given an array of integers where each integer is in the range of 1 to n, inclusive.
- The array has a length of n+1.
- There is exactly one duplicate number in the array, and it can appear more than once.
- We need to find the duplicate number.

**2. Analyze the problem:**
To solve this problem, we can use the Floyd's Tortoise and Hare algorithm, also known as the "Hare and Tortoise" algorithm or the "Cycle Detection" algorithm.

- This algorithm is based on the principle that if we have a cycle in a linked list, we can find it using two pointers: one slow pointer and one fast pointer.
- We can apply this principle to our problem by treating the array as a linked list, where the array elements represent the indices to jump to.
- By initializing two pointers, slow and fast, we can detect the cycle in the array.
- Once the cycle is detected, we can find the entry point of the cycle, which represents the duplicate number.

**3. Design an algorithm:**
Here is the algorithm to solve the problem:

- Initialize two pointers, slow and fast, to the first element of the array.
- Move slow one step at a time and fast two steps at a time until they meet.
- Set the slow pointer back to the first element of the array and keep the fast pointer at the meeting point.
- Move both pointers one step at a time until they meet again. The meeting point is the entry point of the cycle and represents the duplicate number.
- Return the duplicate number.

**4. Explain your approach:**
The approach involves using the Floyd's Tortoise and Hare algorithm to detect the cycle in the array. By treating the array as a linked list and using two pointers, slow and fast, we can find the entry point of the cycle, which represents the duplicate number.

**5. Write clean and readable code:**

python

```
def findDuplicate(nums):
slow = fast = nums[0]
while True:
slow = nums[slow]
fast = nums[nums[fast]]
if slow == fast:
break
slow = nums[0]
while slow != fast:
slow = nums[slow]
fast = nums[fast]
return slow
```

**6. Test your code:**
Let's test the code with different test cases:

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

- Expected output:
`2`

- Explanation: The array represents a linked list with a cycle: 1 -> 3 -> 2 -> 4 -> 2. The duplicate number is 2, which is the entry point of the cycle.

- Expected output:
`nums = [3, 1, 3, 4, 2]`

- Expected output:
`3`

- Explanation: The array represents a linked list with a cycle: 3 -> 4 -> 2 -> 3. The duplicate number is 3, which is the entry point of the cycle.

- Expected output:
`nums = [1, 1, 2]`

- Expected output:
`1`

- Explanation: The array represents a linked list with a cycle: 1 -> 1. The duplicate number is 1, which is the entry point of the cycle.

- Expected output:

**7. Optimize if necessary:**
The solution already follows an optimal approach using the Floyd's Tortoise and Hare algorithm. There are no further optimizations required.

**8. Handle error cases:**
The code assumes that the input array `nums`

is valid and always contains a duplicate number. If the input array is empty or does not have a duplicate number, the behavior of the code is undefined.

**9. Discuss complexity analysis:**

- The time complexity of this solution is O(n), where n is the length of the input array. The Floyd's Tortoise and Hare algorithm guarantees to find the duplicate number in linear time.
- The space complexity is O(1) since we are not using any additional data structures.
- The solution has an optimal time and space complexity given the problem requirements.