Rate this Problem! - Codeforces

Here is a simple problem made by me. Solve it & Give it a rating in comment section if you want.

Problem Name: Range Mex

You are given $$$n$$$ non-negative integers- $$$a_1,a_2,\ldots,a_n$$$. You have to find $$$mex_i$$$ for each $$$1\le i\leq n$$$ such that $$$mex_i$$$ is the mex of all numbers in the array except the $$$i-th$$$ number. e.g. if $$$a=$$${$$${2,5,0}$$$},

$$$mex_1 = mex(a_2,a_3)=mex(5,0)=1$$$

$$$mex_2 = mex(a_1,a_3)=mex(2,0)=1$$$

$$$mex_3 = mex(a_1,a_2)=mex(2,5)=0$$$

Input:

The first line contains a positive number $$$t (1\le t\le 10^4) - $$$ the number of test cases. The description of the test cases follows:

Each test case consists of 2 lines.

The first line contains a positive integer $$$n (1\le n\le 2\cdot 10^5) - $$$indicating the size of array $$$a$$$.

The second line contains $$$n$$$ non-negative integers $$$a_1,a_2,\ldots,a_n (0\le a_i\le 10^9) - $$$ the elements of the array $$$a$$$.

It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$2\cdot10^5$$$.

Output:

For each test case, output $$$n$$$ integers- the $$$i-th$$$ of them indicating $$$mex_i$$$.(i.e. $$$mex_1, mex_2, mex_3,\ldots, mex_n)$$$

Examples:

Input:

Output:

Notes:

Here for the first test case,

$$$mex_1 = mex(1,2,3,4) = 0$$$

$$$mex_2 = mex(0,2,3,4) = 1$$$

$$$mex_3 = mex(0,1,3,4) = 2$$$

$$$mex_4 = mex(0,1,2,4) = 3$$$

$$$mex_5 = mex(0,1,2,3) = 4$$$

Solution

Code

//﷽ [Bismillaahir Rahmaanir Raheem]

#include<bits/stdc++.h>
using namespace std;

#define ll long long int
#define ul unsigned long long int
#define ld long double
#define TT int TC;cin>>TC;for(int ti=1;ti<=TC;ti++)
#define TT1 int TC=1;for(int ti=1;ti<=TC;ti++)
#define fastio ios_base::sync_with_stdio(0); cin.tie(0);
#define YES cout<<"YES"<<endl
#define NO cout<<"NO"<<endl
#define ans_YN if(ans)YES;else NO;
#define pb push_back
#define pr_q priority_queue
#define F first
#define S second
#define MP make_pair
#define UB upper_bound
#define LB lower_bound
#define B begin()
#define E end()
//#define endl "\n"
ll ceill(ll a,ll b){if(a>=0){if(a%b==0)return a/b;else return a/b+1;}else return a/b;}//Here b>0 for being divisor
ll flr(ll a, ll b){if(a>=0){return a/b;} else {if(a%b==0) return a/b; else return a/b-1;}}//Here b>0 for being divisor
ll GCD(ll a, ll b){ ll ans=__gcd(a,b);if(ans<0)ans=-ans;return ans;}
ll LCM(ll a, ll b){ return (a*b)/(GCD(a,b));}
ll rem(ll a, ll b){ if(a>=0) return a%b; else{a=-a; return (b-a%b)%b;}}
int const mod=1e9+7;
int const AND=1073741823;

int main()
{
    fastio
    TT
    {
        ll n;
        cin>>n;
        ll a[n];
        ll mex;
        map<ll,ll>occ;
        for(int i=0;i<n;i++){
            cin>>a[i];
            occ[a[i]]++;
        }

        for(ll i=0;i<=n;i++){
            if(occ[i]==0){
                mex=i;
                break;
            }
        }

        for(int i=0;i<n;i++){
            ll mexx=mex;
            if(occ[a[i]]==1){
                mexx=min(mex,a[i]);
            }
            cout<<mexx<<" ";
        }
        cout<<endl;

        
    }
    return 0;
}