C++ find missing in the second array
Given two arrays A and B of sizes n and m. Find the elements from array A that are not present in array B.
Example
Input :
a[] = {1, 2, 3, 5, 4};
b[] = {1, 2, 3};
Output: 5 4
Explanation:
5 and 4 are present in the first array, but not in the second array.
Input :
a[] = {4, 3, 5, 9, 11};
b[] = {4, 9, 3, 11, 10};
Output: 5
Explanation:
5 is present in the first array, but not in the second array.
- Method 1
A simple approach is to use two loops and check whether the A[i] is present in array B.
CPP code
#include<bits/stdc++.h>
using namespace std;
void findMissingelement(int a[], int b[],
int n, int m) // find missing element in the array B
{
for (int i = 0; i < n; i++) // outer loop
{
int j;
for (j = 0; j < m; j++) // inner loop
if (a[i] == b[j]) // if element is found search element in a[i]
break;
if (j == m) // if we reach end of the array means element is not found
cout << a[i] << " "; // print the element
}
}
int main()
{
int a[] = { 1, 2, 6, 3, 4, 5 }; // array A
int b[] = { 2, 4, 3, 1, 0 }; // array B
int n = sizeof(a) / sizeof(a[0]); // find size of array A
int m = sizeof(b) / sizeof(b[1]); // find size of array B
findMissingelement(a, b, n, m);
return 0;
}
Output
6 5
C code
#include <stdio.h>
void findMissingelement(int a[], int b[],
int n, int m) // find missing element in the array B
{
for (int i = 0; i < n; i++) // outer loop
{
int j;
for (j = 0; j < m; j++) // inner loop
if (a[i] == b[j]) // if element is found search element in a[i]
break;
if (j == m) // if we reach end of the array means element is not found
printf("%d ",a[i]); // print the element
}
}
int main()
{
int a[] = { 1, 2, 6, 3, 4, 5 }; // array A
int b[] = { 2, 4, 3, 1, 0 }; // array B
int n = sizeof(a) / sizeof(a[0]); // find size of array A
int m = sizeof(b) / sizeof(b[1]); // find size of array B
findMissingelement(a, b, n, m);
return 0;
}
Output
6 5
- Method 2
The second approach uses the idea of unordered_set.
In this, insert all the elements of array B in the set and iterate in the first array. If the pointer reaches the end in the set, the element is not present.
Unorderd_set
It is a container that stores values in the form of keys.
Internally, a set implements a red black tree and hence the search, insert and delete is O(1).
Syntax
unordered_set<data_type> variable_name;
Code of unordered_set implementation
#include <iostream>
#include <unordered_map>
using namespace std;
int main()
{
unordered_set<int> s;
s.insert(1);
s.insert(2);
s.insert(3);
for (auto x : s) // print elements of set
cout << x << endl;
}
Output
1
2
3
Method 2 code
#include<bits/stdc++.h>
using namespace std;
void findMissingelement(int a[], int b[],
int n, int m) // function to find the missing element
{
unordered_set <int> s; // create a set
for (int i = 0; i < m; i++)
s.insert(b[i]); // insert array B elements
// Iterate in array A and search a[i] in set s if set reaches the end the element is not present
for (int i = 0; i < n; i++)
if (s.find(a[i]) == s.end())
cout << a[i] << " "; // print the absent element
}
// Driver code
int main()
{
int a[] = { 1, 2, 6, 3, 4, 5 };
int b[] = { 2, 4, 3, 1, 0 };
int n = sizeof(a) / sizeof(a[0]); // find size of the array a
int m = sizeof(b) / sizeof(b[1]);// find size of the array b
findMissingelement(a, b, n, m);
return 0;
}
Output
6 5
Time complexity - O(n+m)
Space complexity - O(n)