Construct MEX array from the given array | C ++ program for the above approach ; Function to construct array B [ ] that stores MEX of array A [ ] excluding A [ i ] ; Stores elements present in arr [ ] ; Mark all values 1 , if present ; Initialize variable to store MEX ; Find MEX of arr [ ] ; Stores MEX for all indices ; Traverse the given array ; Update MEX ; MEX default ; Print the array B ; Driver Code ; Given array ; Given size ; Function call
#include <bits/stdc++.h> NEW_LINE using namespace std ; #define MAXN  100001 NEW_LINE void constructMEX ( int arr [ ] , int N ) { int hash [ MAXN ] = { 0 } ; for ( int i = 0 ; i < N ; i ++ ) { hash [ arr [ i ] ] = 1 ; } int MexOfArr ; for ( int i = 1 ; i < MAXN ; i ++ ) { if ( hash [ i ] == 0 ) { MexOfArr = i ; break ; } } int B [ N ] ; for ( int i = 0 ; i < N ; i ++ ) { if ( arr [ i ] < MexOfArr ) B [ i ] = arr [ i ] ; else B [ i ] = MexOfArr ; } for ( int i = 0 ; i < N ; i ++ ) cout << B [ i ] << ' ▁ ' ; } int main ( ) { int arr [ ] = { 2 , 1 , 5 , 3 } ; int N = sizeof ( arr ) / sizeof ( arr [ 0 ] ) ; constructMEX ( arr , N ) ; return 0 ; }