# Find the Duplicate Number (Leetcode #287)

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.

**Example 1:**

```python
Input: nums = [1,3,4,2,2]
Output: 2
```

**Example 2:**

```python
Input: nums = [3,1,3,4,2]
Output: 3
```

**Example 3:**

```python
Input: nums = [3,3,3,3,3]
Output: 3
```

**Constraints:**

* `1 <= n <= 10<sup>5</sup>`
    
* `nums.length == n + 1`
    
* `1 <= nums[i] <= n`
    
* All the integers in `nums` appear only **once** except for **precisely one integer** which appears **two or more** times.
    

**Follow up:**

* How can we prove that at least one duplicate number must exist in `nums`?
    
* Can you solve the problem in linear runtime complexity?
    

**Answer**

This question is my favorite linked list question so far. It difficulty in my opinion should be Hard since the logic is quite hard to come up with and almost impossible in an interview environment. But if you have seen this algorithms before then the question become much easier.

First, let's break down the question together. Since the question is asking us to do this in constant space we know that we have to solve this using pointers. Since we know that `nums` have a length of n + 1 and we know that nums = \[1,n\] hence we must have a duplicate somewhere.

The hardest part of this question is knowing that it is a linked list question. If we treat each number as a location within the list we will end up with a loop since we have repeated the number.

For example

![](https://cdn.hashnode.com/res/hashnode/image/upload/v1722093092561/52a6c39b-b872-474d-963e-7e54f3595bbd.png align="center")

Now the next part is quite counterintuitive. We will break the answer into two part

First, send out a slow and fast pointer where 2slow = fast and find the interception

Second restart keep the slow pointer and start another slow pointer and the beginning and with the same speed the intersection will be the duplicate number.

![](https://cdn.hashnode.com/res/hashnode/image/upload/v1722093286610/f090ef35-4230-4ec8-a6b8-3595d748c47e.png align="center")

Following this diagram the first step will give you the intersection of 5 and then since we have proven the p == x the second step will give us 1 which is the repeated number.

```python
class Solution(object):
    def findDuplicate(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        #first step Slow and Fast pointer
        slow = fast = 0
        while True:
            slow = nums[slow]
            fast = nums[nums[fast]]
            if slow == fast:
                break
        #secound step Slow and Slow2
        slow2 = 0
        while True:
            if nums[slow] == nums[slow2]:
                return nums[slow]
            slow = nums[slow]
            slow2 = nums[slow2]
```

**Time Complexity**

O(N). In the first step in the worst case we will go through the nums twice O(2n) and second step worst case we go through the nums ounce. Hence O(2n) + O(N) = O(N)

**Space Complexity**

O(1) Since we are only storing pointers