# Solution: Find The Duplicate Number

Let's solve the Find The Duplicate Number problem using the the Fast and Slow pattern.

## We'll cover the following

## Statement

Given an array of positive numbers, `nums`

, such that the values lie in the range $[1, n]$, inclusive, and that there are $n+1$ numbers in the array, find and return the duplicate number present in `nums`

. There is only one repeated number in `nums`

.

Note:You cannot modify the given array`nums`

. You have to solve the problem using only constant extra space.

**Constraints:**

- $1 \leq n \leq 10^3$
`nums.length`

$= n + 1$- $1 \leq$
`nums[i]`

$\leq n$ - All the integers in
`nums`

are unique except for one integer that will appear more than once.

## Solution

We solve this problem using fast and slow pointers technique, without modifying the `nums`

array and using only constant extra space.

For this problem, the duplicate number will create a cycle in the `nums`

array. The cycle in the `nums`

array helps identify the duplicate number.

To find the cycle, weâ€™ll move in the `nums`

array using the $f(x) = nums[x]$ function, where $x$ is the index of the array. This function constructs the following sequence to move:

$x, \space nums[x], \space nums[nums[x]], \space nums[nums[nums[x]]], \space ...$

In the sequence above, every new element is an element in `nums`

present at the index of the previous element.

Letâ€™s say we have an array, $[2, \space 3,\space 1,\space 3]$. Weâ€™ll start with $x=nums[0]$, which is $2$, present at the $0^{th}$ index of the array and then move to $nums[x]$, which is $1$, present at the $2^{nd}$ index. Since we found $1$ at the $2^{nd}$ index, weâ€™ll move to the $1^{st}$ index, and so on. This example shows that if weâ€™re given an array of length $n+1$, with values in the range $[1,\space n]$, we can use this traversal technique to visit all the locations in the array.

The following example illustrates this traversal:

Level up your interview prep. Join Educative to access 80+ hands-on prep courses.