DAY 108 - Find Duplicate
Tags: programming, tutorial, datastructures, algorithms
Published: 2023-09-19 18:26:51

Hey  Guys! Welcome back to another 100DaysOf Code day.
We are going to do another daily leetcode question today.

## Question: [Find Duplicate](https://leetcode.com/problems/find-the-duplicate-number/description/?envType=daily-question&envId=2023-09-19)

_Given an array of integers nums containing n + 1 integers where each integer is in the range [1, n] inclusive._

_There is only one repeated number in nums, return this repeated number._

_You must solve the problem without modifying the array nums and uses only constant extra space._

---

### Examples:

**Example 1:**

> **Input:** nums = [1,3,4,2,2]
> **Output:** 2


**Example 2:**

> **Input:** nums = [3,1,3,4,2]
> **Output:** 3

---

## Understanding the Problem

Before diving into the code, let's break down the problem and understand what's expected:

- You are given an array `nums` containing n + 1 integers.

- Each integer in the array is between 1 and n (inclusive).

- There is only one integer that appears more than once in the array.

- Your task is to find and return this duplicate integer.

## The Approach

To efficiently solve this problem, we can use the Floyd's Tortoise and Hare algorithm, which is also known as the cycle detection algorithm. Here's how it works:

1. We initialize two pointers, `slow` and `fast`, both initially pointing to the first element of the array.

2. We use a loop to advance these pointers. The `slow` pointer moves one step at a time, while the `fast` pointer moves two steps at a time. This simulates two runners racing along the array.

3. If there is a duplicate number in the array, the pointers will eventually enter a cycle, meaning they will meet at the same position.

4. Once the pointers meet inside the cycle, we reset one of the pointers, let's say `fast`, to the beginning of the array, while keeping the other pointer (`slow`) inside the cycle.

5. We then advance both pointers at the same rate (one step at a time). When they meet again, it will be at the entrance of the cycle.

6. The position where the two pointers meet for the second time is the location of the duplicate number.

7. We return this duplicate number as our result.

---


## Code:

```cpp

class Solution {
public:
    int findDuplicate(vector<int>& nums) {
        int slow = nums[0];
        int fast = nums[0];
        
        do {
            slow = nums[slow];
            fast = nums[nums[fast]];

        } while(slow != fast);

        fast = nums[0];

        while(slow != fast){
            slow = nums[slow];
            fast = nums[fast];
        }
    return slow;
    }
};

```

---

## Time and Space Complexity

Let's analyze the time and space complexity of our solution:

- **Time Complexity**: The Floyd's Tortoise and Hare algorithm runs in O(N) time, where N is the length of the array. This is because both pointers move through the array at different speeds, but the fast pointer covers the cycle at most twice.

- **Space Complexity**: We use only a constant amount of extra space to store the `slow` and `fast` pointers. Therefore, the space complexity is O(1).