# 1. Introduction

"Find the Duplicate Number" is a challenging problem that involves finding a repeating number in an array of integers. The constraints of not modifying the array and using only constant extra space add to its complexity. This problem is commonly used to test the understanding of array manipulation and cycle detection algorithms.

## Problem

Given an array *nums* containing *n + 1* integers, each integer is in the range *[1, n]* inclusive. There is exactly one number that is repeated in *nums*, and the task is to find and return this repeated number. The solution must not modify the array and should use only constant extra space.

# 2. Solution Steps

1. Use the Floyd's Tortoise and Hare (Cycle Detection) algorithm to find the duplicate number.

2. Initialize two pointers, *slow* and *fast*, both starting from the first element.

3. Move *slow* pointer by one step and *fast* pointer by two steps until they meet.

4. Once they meet, initialize another pointer *ptr* at the start of the array.

5. Move both *ptr* and *slow* one step at a time until they meet; the meeting point is the duplicate number.

6. Return the duplicate number found.

# 3. Code Program

```
def findDuplicate(nums):
slow = fast = nums[0]
while True:
slow = nums[slow]
fast = nums[nums[fast]]
if slow == fast:
break
ptr = nums[0]
while ptr != slow:
ptr = nums[ptr]
slow = nums[slow]
return ptr
# Example Usage
print(findDuplicate([1,3,4,2,2])) # Output: 2
print(findDuplicate([3,1,3,4,2])) # Output: 3
```

### Output:

2 3

### Explanation:

**1. Floyd's Tortoise and Hare Algorithm**: Utilizes cycle detection to find the duplicate.

**2. Two-Pointer Approach**: *slow* and *fast* pointers are used to detect a cycle in the array.

**3. Detecting the Duplicate**: The meeting point of *slow* and *ptr* indicates the start of the cycle, which is the duplicate number.

**4. Constant Space Usage**: The algorithm uses only a few extra pointers, ensuring O(1) space complexity.

**5. No Array Modification**: The array remains unmodified throughout the process.

**6. Efficiency**: Provides an efficient solution with O(n) time complexity.

**7. Practical Application**: Illustrates a technique for cycle detection in arrays, applicable in various contexts like data analysis.

## Comments

## Post a Comment