Program to Find Duplicate Element of an Array.

Given a positive integer array of sizes n and we need to find the element that appears more than one time in the given array. If no such element is present then return -1.

Example 1:

Input: arr[] = {9, 2, 7, 3, 10, 2}
Output: 2

Explanation: 2 appears more than one times.

Input: arr[] = {4, 2, 7, 3, 10, 21}
Output: -1
Explanation: All elements are unique, not duplicate element found.

Approach 1: Brute Force.

We can find the duplicate element in the given array but run two nested loops where the first loop will pick the element one by one and the inner loop will compare that element with all remaining elements of the array to check if any duplicate element exists.

Steps to solve the problem:

Run two nested loops, the first loop will run from i = 0 to i = n-1 and the second loop will run from j = i+1 to j = n-1.
If at any moment, arr[i] == arr[j] it means a duplicate element exist,s and then prints the duplicate element.

C++ code Implementation:

//C++ code to find duplicate elements of array
#include<bits/stdc++.h>
using namespace std;

//function to find duplicate element in array
int duplicate(int arr[], int n){
    int ans;

    for(int i = 0; i < n; i++){
        for(int j = i+1; j < n; j++){
            if(arr[i] == arr[j]){
                ans = arr[i];
                break;
            }
        }
    }
    return ans;
}

int main(){
    
    int arr[] = {9, 2, 7, 3, 10, 2};
    //size of the given array
    int n = sizeof(arr)/sizeof(arr[0]);
    
    cout<<"The element present more than one time: "<<duplicate(arr, n);

    return 0;
}

Output:

The element present more than one time: 2

Time Complexity: O(n^2)
Space Complexity: O(1)

Approach 2: Using a Hash Table (Optimized).

For this approach, we are going to use an unordered map (internally implemented using Hash Table) that is an associated container used to store data in the form of Key and Value pair.

Steps to solve the problem:

Declare a unordered_map<int, int> in which the key and value type is an integer.
Traverse the array and take each element as Key and store their count as a value to that key.
If you found any key with a value greater than 1 then it means there exists a duplicate element in the array.
Print that key with having count greater than 1.

C++ code Implementation:

//C++ code to find duplicate elements of array using Hash Table
#include<bits/stdc++.h>
using namespace std;

//function to find duplicate element in array
int duplicate(int arr[], int n){
    int ans;
    unordered_map<int, int> mp{0};

    for(int i = 0; i < n; i++){
        mp[arr[i]]++;
    }

    for(auto it: mp){
        if(it.second > 1){
          ans = it.first;
          break;
        }    
    }
    return ans;
}

int main(){
    
    int arr[] = {9, 2, 7, 3, 10, 2};
    //size of given array
    int n = sizeof(arr)/sizeof(arr[0]);
    
    cout<<"The element present more than one times: "<<duplicate(arr, n);

    return 0;
}

Output:

The element present more than one time: 2

Time Complexity: O(n) As we need to traverse the array only one time to get the count of each unique element and there is no nested loop required.
Space Complexity: O(n) As we are using extra n space for storing the count of each unique element.

Also see:

(getButton) #text=(Program to Reverse Array Elements) #icon=(link) #color=(#2339bd)

(getButton) #text=(Program to Find Kth Smallest Element of an Array) #icon=(link) #color=(#2339bd)

Program to Find Duplicate Element of an Array.

Approach 1: Brute Force.

Approach 2: Using a Hash Table (Optimized).

No comments:

Post a Comment