# Find The Duplicate Number Problem

## Description

LeetCode Problem 287.

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

There is only one repeated number in nums, return thisrepeatednumber.

You must solve the problem without modifying the array numsand uses only constant extra space.

Example 1:

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

Example 2:

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

Example 3:

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

Example 4:

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

Constraints:

• 1 <= n <= 10^5
• 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.

## Sample C++ Code

``````1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public:
int findDuplicate(vector<int>& nums) {
int len = nums.size();
if (len == 0)
return 0;

int p1 = nums[0], p2 = nums[nums[0]];
while (p1 != p2) {
p1 = nums[p1];
p2 = nums[nums[p2]];
}
p1 = 0;
while (p1 != p2) {
p1 = nums[p1];
p2 = nums[p2];
}
return p1;
}
};
``````