# 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.

1. 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
1. 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)