# Solution: Find The Duplicate Number

Let's solve the Find The Duplicate Number problem using the Fast and Slow Pointers 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 70+ hands-on prep courses.