# Find the Duplicate Number

## Problem

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

There is only **one duplicate number** in `nums`, return *this duplicate number*.

{% hint style="info" %}
For example:

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

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

```
Input: nums = [1,1,2]
Output: 1
```

{% endhint %}

## Solution

```
def find_duplicate(nums):
    i = 0
    while i < len(nums):
        if nums[i] != i+1:
            j = nums[i] - 1
            if nums[i] != nums[j]:
                nums[i], nums[j] = nums[j], nums[i]
            else:
                return nums[i]
        else:
            i+=1
    return -1
    
    
#Following cyclic sort, we will try to place each 
number on its correct index.
#Since there is only one duplicate, if while swapping
#the number with its index both the numbers being 
#swapped are same, we have found our duplicate!

#Time: O(n)
#Space: O(1)

```