This content originally appeared on DEV Community and was authored by sachin26
hi Dev,
today we are going to solve the 10th problem from the sheet, which is Find the duplicate in an array.
lets start....
Problem Statement :-
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.
Solution 1
using sorting, we can easily find the duplicate number by linearly checking the one which has the same at the next position.
step-1 first sort the array.
step-2 run a loop from i=0 to n,then
if
nums[i] == nums[i+1], then return thenums[i]
step-3 end.
Java
class Solution {
public int findDuplicate(int[] nums) {
Arrays.sort(nums);
for(int i=0; i<nums.length;i++){
if(nums[i] == nums[i+1]) return nums[i];
}
return 0;
}
}
Time Complexity : O(nlogn)
Space Complexity : O(1)
Solution 2
Since we know that. The range of the array’s number is 1 to N. so, we can use the array indices for marking the visited number.
step-1 run a loop from i=0 to N, then
1. get the i'th number from the array.
index = nums[i]2. mark the index value, as visited, by multiply -1
nums[abs(index)] *= -13. Check, is it already marked, then return the number
if nums[abs(index)] > 0, then return abs(nums[i])
step-2 end.
Java
class Solution {
public int findDuplicate(int[] nums) {
for(int i=0;i<nums.length;i++){
int index = Math.abs(nums[i]) - 1;
nums[index] *= -1;
if(nums[index] > 0) return Math.abs(nums[i]);
}
return 0;
}
}
Time Complexity : O(n)
Space Complexity : O(1)
Solution 3
this problem can be solve by using Binary Search algorithm
Since the numbers are 1 to N,traverse through the array and count the numbers which are less than or equal to mid .
If the count is less than mid, then duplicate number should be on the right side.
If the count is greater than mid, then duplicate number should be on the left side.
then narrow down the search space by updating the left & right value.
lets understand this algo step by step.
step-1 initialise the variables left=0, right=arrLen
step-2 run a loop if left < right, then
1. initialise
count=02. calculate the mid
mid = (left + right) / 23. run a loop from
i=0ton, then
if nums[i] <= mid, thencount++4. if
count > midthen updateright
right = mid5. if
count < midthen updateleft
left = mid+1
step-3 return the left variable.
step-4 end.
Java
class Solution {
public int findDuplicate(int[] nums) {
int left=0, right=nums.length-1;
while(left < right){
int count =0;
int mid = (left + right) / 2;
for(int i=0;i<nums.length;i++)
if(nums[i] <= mid) count++;
if(count > mid)
right = mid;
else
left = mid+1;
}
return left;
}
}
Time Complexity : O(nlogn)
Space Complexity : O(1)
thank you for reading this article, if you find any mistakes, let me know in the comment section
This content originally appeared on DEV Community and was authored by sachin26
sachin26 | Sciencx (2022-01-01T13:20:32+00:00) Striver’s SDE Sheet Journey – #10 Find the duplicate in an array. Retrieved from https://www.scien.cx/2022/01/01/strivers-sde-sheet-journey-10-find-the-duplicate-in-an-array/
Please log in to upload a file.
There are no updates yet.
Click the Upload button above to add an update.