Find elements which are present in first array and not in second in C++

We are given two arrays and we have to find numbers that are present in the first array, but not present in the second array.

Elements that are present in the first array and not in second in C++

Example:

arr1[]={3,4,5,9,10};
arr2[]={3,1,10,9,6}; 

The answer will be 4 5 
Since 4 and 5 are present in arr1 but not present in arr2. 
x[]={9,56,75,65,90}; 
y[]={90,4,56,75,65}; 

The answer will be 9 
Since 9 is present in x but not present in y.

 

Approach 1: Brute Force

The brute force approach is simple. Using two loops find if the element is present in the second array or not.

#include<iostream>
using namespace std; 

void findElement(int *arr1 , int *arr2, int n1, int n2){

    for(int i=0;i<n1;i++){
        for(int j=0;j<n2;j++){
            if(arr1[i]==arr2[j]){
                break;
            }

            if(j==n2-1){
                cout<<arr1[i]<<" ";
            }
        }
    }
}

int main() 
{ 
  int arr1[]={9,56,75,65,90};
  int arr2[]={90,4,56,75,65};
  int n = sizeof(arr1) / sizeof(int); 
  int m = sizeof(arr2) / sizeof(int); 
  findElement(arr1, arr2, n, m); 
  return 0; 
} 

Output:

9

Time complexity: O(n^2). For each element, we try to find its element by looping through the second array which takes O(n)* time. Therefore, the time complexity is O(n^2).

 

Approach2: Using hashing

To improve time complexity, we need a more efficient way to check if the element present in the second array or not. So we use the hash table.

#include<iostream>
#include<unordered_set>
using namespace std; 

void findElementFast(int *arr1, int *arr2,int n1, int n2) { 
    unordered_set <int> u; 
    for (int i = 0; i < n1; i++){
    u.insert(arr2[i]);
  }
        
    for (int j = 0; j < n2; j++){
    if (u.find(arr1[j]) == u.end()){
      cout << arr1[j] << " "; 
    }
  }        
} 
  
int main() 
{ 
  int arr1[]={3,4,5,9,10};
  int arr2[]={3,1,10,9,6};
  int n = sizeof(arr1) / sizeof(int); 
  int m = sizeof(arr2) / sizeof(int); 
  findElementFast(arr1, arr2, n, m); 
  return 0; 
} 

Output:

4 5

Time complexity: O(n).Since the hash table reduces the time to find the element to , the time complexity is .

Leave a Reply

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