Find the duplicate number

(LeetCode : Medium)

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

Example 3:

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

Example 4:

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.

I am going to discuss four types of approaches here starting from Brute force to the optimized approach. Let’s begin :

Approach 1

Run two loops one inside the other to find if it satisfies the condition arr[i]==arr[j], satisfies or not.

Time Complexity-O(n*n), Space Complexity-O(1)

PS : Try to code this by yourself, I have given the logic above.

Approach 2

Step 1: Sort the array, Time Complexity-O(nlogn)

Step 2: Run a loop to find if the adjacent elements are the same or not?

TC-O(n), so total Time Complexity-O(nlogn)+O(n)

Space Complexity-O(1)

PS : Try to code this by yourself, I have given the logic above.

Approach 3

Using the concept of pigeon principle/ binary search.

class Solution {
public:
int findDuplicate(vector& nums) {
int n=nums.size();
int left=1,right=n-1,c,mid;
    
    while(left<right)
    {
        mid=(left+right)/2;
        c=0;
        
        for(int i=0;i<n;i++)
            if(nums[i]<=mid)c++;
        
        if(c>mid)right=mid;
        else left=mid+1;
    }
    return left;
   }
};
Time Complexity - O(nlogn)
Space Complexity - O(1)
PS : I urge you to do a dry run for the above code for a clear understanding. If you face any issues feel free to comment below and ask. 

Approach 4

Using the approach of hashing

Step 1: Use another array for storing the frequency of the elements. The element whose frequency is greater than 1, that is the repeating/ duplicate element.

Time Complexity-O(n), Space Complexity-O(n)

Approach 5

(Linked List cycle method)

class Solution {
public:
    int findDuplicate(vector<int>& nums) {
        int slow = nums[0];
        int fast = nums[0];
        
        do{
            slow = nums[slow];
            fast = nums[nums[fast]];
        }while(slow!=fast);
        
        fast = nums[0];
        
        while(slow!=fast)
        {
            slow = nums[slow];
            fast = nums[fast];
        }
        return slow;
    }
};
Let us do a dry run to understand better the approach behind the code :
nums = [1,3,4,2,2]
slow = nums[0] = 1
fast = nums[0] = 1
slow = nums[1] = 3
fast = nums[nums[1]] = nums[3] = 2
since these two are not equal we update the values ,
slow = nums[3] = 2
fast = nums[nums[2]] = nums[4] = 2
Now since these are equal , we exit the loop.
Now fast = nums[0] = 1
slow!=fast , 
slow = nums[2] = 4
fast = nums[1] = 3
slow!=fast so ,
slow = nums[4] = 2
fast = nums[3] = 2
Now slow and fast are equal so , the repeating element is 2.
Intution : The basic thinking is that we keep two counter variables, slow is incremented by +1 and fast by +2 and at one point they will be pointing to the repeating elements, which is returned by the slow pointer. 

Hope this article helps! Stay tuned for more!!! Keep coding 💻🙌

Since you enjoyed reading my blog , why not buy me a coffee and supoort my work here!! https://www.buymeacoffee.com/sukanyabharati ☕