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.
Follow up:
- 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]