# Leet Code : Find the Duplicate Number / Element C++ ,Java , Python Solution:

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:

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

Example 2:

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

Constraints:

• `1 <= n <= 105`
• `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.

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

## C++ Solution:

``````//solution BY Nilesh Vishnu Raut ...Codewithnilesh

#include <bits/stdc++.h>
using namespace std;

int main() {
string arr[]={"nilesh" ,"Raut" , "nilesh" ,"Raut" };
unordered_map<string,int>m;
for(int i=0;i<5;i++){
m[arr[i]]++;
}

int max=0;
string win;

for(auto x:m){
if(x.second>max){
max=x.second;
win=x.first;

}
else if(max==x.second) {
if(x.first<win){
win=x.first;
}
}

}
cout<<win;
return 0;
}``````

## Java Solution :

`````` public int findDuplicate_fastSlow(int[] nums) {
int slow = 0;
int fast = 0;
do {
slow = nums[slow];
fast = nums[nums[fast]];
} while (slow != fast);

slow = 0;
while (slow != fast) {
slow = nums[slow];
fast = nums[fast];
}

return slow;
}``````

## Python Solution :

``````def findDuplicate(self, list):
i=0
n=len(list)

#STEP 1- Cyclic sort list
while(i<n):
if(list[i]!= i+1):
correct_pos= list[i]-1

if(list[i]== list[correct_pos]):
i+=1
else:
list[i],list[correct_pos]= list[correct_pos],list[i]
else:
i+=1

#STEP 2 - Finding element != index +1 - That must be the repeated element.
i=0
for i in range(0,n):
if list[i]!= i+1:
return list[i]`````` I am Nilesh,3+ years Exp of SEO, content writing, and keyword research. Also rocks it as a software dev with skills in OS, web dev, Flask, Python, C++, data structures, and algorithms. 3 on Leetcode, 5*on Hackerrank more platform.