Find the Duplicate Number - Python Solution

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.