C++ Tutorial Index

C++ Tutorial C++ History C++ Installation C++ First Program C++ cin and cout C++ Data type C++ Variable C++ operator C++ Keywords

C++ Control Statements

C++ If C++ Nested if C++ If-else C++ If-else-if C++ Switch C++ Break C++ Continue C++ Goto C++ For loop C++ While loop C++ Do while loop

C++ Functions

C++ Call by Value C++ Call by Reference C++ Recursion Function C++ Inline function C++ Friend function

C++ Arrays

Single dimension array Two dimension array

C++ Strings

C++ Strings

C++ Inheritance

C++ Inheritance Single level Inheritance Multilevel Inheritance Multiple Inheritance Hierarchical Inheritance Hybrid Inheritance

C++ Polymorphism

C++ Polymorphism C++ Overloading C++ Overriding C++ Virtual Function

C++ Pointers

C++ Pointers C++ this pointer

C++ Exception Handling

C++ Exception Handling

C++ Constructors

C++ Constructors Default Constructor Parameterize Constructor Copy constructor Constructor Overloading Destructor

C++ File Handling

C++ File Handling C++ Writing to file C++ Reading file C++ Close file

Miscellaneous

C Vs C++ C++ Comments C++ Data Abstraction C++ Identifier C++ Memory Management C++ Storage Classes C++ Void Pointer C++ Array To Function C++ Expressions C++ Features C++ Interfaces C++ Encapsulation std::min in C++ External merge sort in C++ Remove duplicates from sorted array in C++ Precision of floating point numbers Using these functions floor(), ceil(), trunc(), round() and setprecision() in C++ C++ References C++ Friend Functions C++ Mutable keyword Unary Operators in C++ Initialize Array of objects with parameterized constructors in C++ Differences between #define & const in C/C++ C++ Program to Implement Shell Sort C++ Program to Implement Merge Sort Storage Classes in C Vector resize() in C++ Passing by Reference Vs. Passing by the pointer in C++ Free vs delete() in C++ goto statement in C and C++ C++ program to read string using cin.getline() C++ String Concatenation Heap Sort in C++ Swap numbers in C++ Input Iterators in C++ Fibonacci Series in C++ C ++ Program: Alphabet Triangle and Number Triangle C++ Program: Matrix Multiplication C++ Program to Print Fibonacci Triangle Stack in C++ Maps in C++ Queue in C++ C++ Bitset C++ Algorithms Priority Queue in C++ C++ Multimap C++ Deque Function Pointer in C++ Sizeof() Operators in C++ C++ array of Pointers free() Vs delete in C Timsort Implementation Using C++ CPP Templates C++ Aggregation C++ Enumeration C++ Math Functions C++ Object Class C++ Queue Initialize Vector in C++ Vector in C++ C++ STL Components Function overloading in C++ C++ Maximum Index Problem C++ find missing in the second array C++ Program to find the product array puzzle C++ Program To Find Largest Subarray With 0 Sum C++ Program To Move All Zeros To The End Of The Array C++ Program to find the element that occurs once C++ Program to find the largest number formed from an array Constructor Vs Destructor C++ Namespaces C++ OOPs Concept C++ Static C++ Structs C++ Try-Catch C++ User Defined Exceptions C++ Virtual Destructor C++ vs C# Malloc() and new in C++ Palindrome Number Program in C++ Snake Code in C++ Splitting a string in C++ Structure Vs Class in C++ Virtual Function Vs Pure Virtual Function C++ Bidirectional Iterators C++ Forward Iterators C++ Iterators C++ Output Iterators C++ Range-based For Loop Converting string into integer in C++ LCM Program in C++ Type conversion in C++ Add two numbers using the function in C++ Advantage and disadvantage friend function C++ Armstrong Number Program in C++ ATM machine program in C++ using functions Binary to Decimal in C++ Bit Manipulation in C++ C++ Constructor C++ Dijkstra Algorithm Using the Priority Queue C++ int into String C++ Signal Handling Decimal to Binary in C++ Decimal to Hexadecimal in C++ Decimal to Octal in C++ Factorial Program in C++ Function in C++ Hexadecimal to Decimal in C++ Octal to Decimal in C++ Reverse a Number in C++ Structure Vs Class in C++ C++ Forward Iterators C++ Output Iterators C++ Prime number program Char Array to String in C++ Constructor Overloading in C++ Default arguments in C++ Different Ways to Compare Strings in C++ Dynamic Binding in C++ Program to convert infix to postfix expression in C++ SET Data Structure in C++ Upcasting and Downcasting in C++ Reverse an Array in C++ Fast Input and Output in C++ Delete Operator in C++ Copy elision in C++ C++ Date and Time C++ Bitwise XOR Operator Array of sets in C++ Binary Operator Overloading in C++ Binary Search in C++ Implementing the sets without C++ STL containers Scope Resolution Operator in C++ Smart pointers in C++ Types of polymorphism in C++ Exception Handling in C++ vs Java Const Keyword in C++ Type Casting in C++ Static keyword in C++ vs Java Inheritance in C++ vs Java How to concatenate two strings in C++ Programs to Print Pyramid Patterns in C++ swap() function in C++ Structure of C++ Program Stringstream in C++ and its applications rand() and srand() in C / C++ C++ Ternary Operator C++ Scope of Variables While Loop Examples in C++ Star pattern in C++ using For Loops For Loop Examples in C++ Do-While Loop Examples in C++ Top 5 IDEs for C++ That You Should Try Once Assertions in C/C++ C++ Convert Int to String Continue in C++ While loop Diamond Pattern in C++ using For Loop How to Reverse a String in C++ using Do-While Loop How to Reverse a String in C++ using For Loop How to Reverse a String in C++ using While Loop Infinite loop in C++ Loops in C++ Returning Multiple Values from a Function using Tuple and Pair in C++ wcscpy(), wcslen(), wcscmp() Functions in C++

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)



ADVERTISEMENT
ADVERTISEMENT