Arrays: Given an array find the duplicate number

Problem Statement:

You are given an array of integers having “n+1” integers. The integers in the array will be from [1, n].

There will be one duplicate number and return the duplicate number.

Example:

Input: arr = {1, 2, 1}

Output: 1

Solution:

We can solve this problem in number of different methods. Some of the methods are as below:

1. Binary Search
2. By 2 pointer method

1. Binary Search method

This method is very simple.

WKT there is a duplicate number, so we do a binary search on [1:N], then count the number of elements.

If the element count is greater than mid, then the duplicate element is on the left side else

the duplicate element is on the right side. Accordingly narrow the space.

Let us analyze the code with the help of an example:

We have an array: [1, 3, 4, 2, 2]

Initial Pass 1:

Low = 1
High = 4
Mid = 2

Now it will compare all the elements from the array with the mid index value.

So compare all the elements with the mid index “2” and count the number of elements that are greater than mid element.

At the end of the Pass 1, there are 3 elements that are greater than or equal to mid index value.

They are [4, 2, 2]

So count = 3. As the count is greater than the mid, we move towards left side. Change the right pointer.

Pass 2:

Low = 1
High = 2
Mid = 1

Now again count the elements that are greater than the mid index i.e “1”.

There is only one element i.e 4. So change the low value to mid+1, i.e 2.

Now the while loop condition “(low<high)” will be false because low = 2 and high = 2.

Return the value of low. That will be the duplicate element.

In this method Time Complexity is : O(nlogn), Space Complexity is : O(1)

Solution in C++

The duplicate using binary search is 2


#include <vector>    
#include <algorithm>  
//visit www.ProDeveloperTutorial.com for 450+ solved questions  
#include <iostream>    
#include <queue>

using namespace std;  

int find_duplicate_binary_search(vector<int>& nums) 
{
    int n=nums.size()-1;
    int low=1;
    int high=n;
    int mid;
    while(low<high)
    {
        mid=(low+high)/2;
        
        int count=0;
        for(int num:nums)
        {
            if(num<=mid) 
                count++;
        }
        if(count>mid) 
            high=mid;
        else 
            low=mid+1;     
        
    }
    return low;
}


int main() 
{ 
    std::vector<int> v = {1, 3, 4, 2, 2}; 

    cout << "\nThe duplicate using binary search is "
        << find_duplicate_binary_search(v); 
    return 0; 
}

 

2. By 2 pointer method

This method is very similar to finding a cycle in linked list by using fast and slow pointer approach.

This method has 3 steps:

Step 1: Create an array cycle.

Step 2: Start both fast and slow pointer and continue till they both meet at a point.

Step 3: Once they both meet at a point, move the fast pointer to the beginning of the array and then move both the pointer one step at a time. The element in the index where they both meet is the duplicate element.

We shall look at the above 3 steps with help of an example:

We shall take an example

[1, 3, 4, 2, 2]

Step 1: Create a cyclic array

Create a cyclic array as x -> nums[x] -> nums[nums[x]] -> …

i.e

At index 0, element is 1. Write down 1.

1 ->

Now, go to index 1 and write down the element. Next go to the index of the element and write down that element i.e

At index 1, the element is 3.

1 -> 3

Now go to index 3 and write down the element i.e 2.

1 -> 3 -> 2

Similarly create a cyclic linked list as below:

1 -> 3 -> 2 -> 4 -> 2

Once you create a cycle, move the fast pointer to the initial of the array, then move both fast and slow pointer one step at a time.

The element at the index where they meet is the duplicate element.

Solution in C++

#include <vector>    
#include <algorithm>  
//visit www.ProDeveloperTutorial.com for 450+ solved questions  
#include <iostream>    
#include <queue>

using namespace std;  

int find_duplicate_fast_slow_pointer(vector<int>& nums)
{
   if (nums.size() > 1)
   {
      int slow = nums[0];
      int fast = nums[nums[0]];

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

      fast = 0;
      while (fast != slow)
      {

         fast = nums[fast];
         slow = nums[slow];
      }
      return slow;
   }
   return -1;
}


int main() 
{ 
    std::vector<int> v = {1, 3, 4, 2, 2}; 

    cout << "\nThe duplicate using fast and slow pointer is "
        << find_duplicate_fast_slow_pointer(v)<<endl; 
    return 0; 
}

Output:

The duplicate using fast and slow pointer is 2

 

Write a Comment

Leave a Comment

Your email address will not be published. Required fields are marked *