Find the Duplicate Number Leetcode Solution
Find the Duplicate Number Leetcode Problem :
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.
Find the Duplicate Number Leetcode Solution :
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.
Example 1:
- Input: nums = [3,1,3,4,2]
- Output: 3
Intuition :
We use the linked list by using the technique to find cycle in the list. The element to which both the pointers meet will be the element repeated in the list.
Approach :
We start by initializing a slow pointer and a fast pointer and then move the fast pointer with 2x the speed of the slow pointer until they both point to the same element. To prevent any bottlenecks or overflows we initialize the fast pointer again to the first element of the list and then again moveboth the pointers with the same speed to end with the repeated element.
Prime Course Trailer
Related Banners
Get PrepInsta Prime & get Access to all 200+ courses offered by PrepInsta in One Subscription
Code :
class Solution {
public:
int findDuplicate(vector< int>& nums) {
int slow=nums[0], fast=nums[0];
do{
fast = nums[nums[fast]];
slow = nums[slow];
}while(fast != slow);
fast=nums[0];
while(slow!=fast){
slow=nums[slow];
fast=nums[fast];
}
return slow;
}
};
class Solution {
public int findDuplicate(int[] nums) {
int[] arr=new int[10000];
int res=0;
for(int i : nums){
int bucket = i/32;
int bit = i%32;
int k = arr[bucket] & (1<< bit);
if(k==0){
arr[bucket]=arr[bucket] | (1<< bit);
}else{
res=i;
break;
}
}
return res;
}
}
class Solution:
def findDuplicate(self, nums: List[int]) -> int:
slow,fast=0,0
while True:
slow=nums[slow]
fast=nums[nums[fast]]
if slow==fast:
break
slow2=0
while True:
slow=nums[slow]
slow2=nums[slow2]
if slow==slow2:
return slow
Get over 200+ course One Subscription
Courses like AI/ML, Cloud Computing, Ethical Hacking, C, C++, Java, Python, DSA (All Languages), Competitive Coding (All Languages), TCS, Infosys, Wipro, Amazon, DBMS, SQL and others
Login/Signup to comment