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:↵
↵
```5↵
5↵
0 1 2 3 4↵
5↵
1 0 2 5 9↵
2↵
1 2↵
3↵
1 0 2↵
4↵
4 7 0 1 ↵
```↵
↵
Output:↵
↵
```0 1 2 3 4 ↵
1 0 2 3 3 ↵
0 0 ↵
1 0 2 ↵
2 2 0 1 ↵
```↵
↵
**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$↵
↵
↵
<spoiler summary = "Solution">↵
↵
We can easily think of Brute Force Solution of getting mex for each index with a Complexity of $O(n^2)$ resulting in TLE. So For each index $i$, the $mex_i$ has to be determined in $O(1)$ or $O(\log{}{n})$. For this, we have to determine the mex of the whole array & for each index we will compare with this mex to get $mex_i$.↵
↵
Let, $mex = mex(a_1,a_2,\ldots,a_n)$. That means all numbers from $0$ to $mex-1$ remains in the array!↵
↵
Now for index $i$, if occurrence of $a_i$, $occ[a[i]]\gt 1$, then it does not affect the mex. So here $mex_i = mex$. But if $occ[a[i]]==1$, then its absence will change the mex if $mex\gt a[i]$. Then $mex_i = a[i]$. But if $mex\le a[i], mex_i=mex$. Ultimately, we get $mex_i=min(mex,a[i])$.↵
↵
**Complexity:** ↵
↵
$O(n)$ [If you use array for occurrence of each element of the array]↵
↵
$O(n\cdot \log{}{n})$ [If you use map for occurrence of each element of the array]↵
↵
</spoiler>↵
↵
↵
<spoiler summary="Code">↵
```c++↵
//﷽ [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;↵
}↵
```↵
↵
</spoiler>↵
↵
↵
**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:↵
↵
```5↵
5↵
0 1 2 3 4↵
5↵
1 0 2 5 9↵
2↵
1 2↵
3↵
1 0 2↵
4↵
4 7 0 1 ↵
```↵
↵
Output:↵
↵
```0 1 2 3 4 ↵
1 0 2 3 3 ↵
0 0 ↵
1 0 2 ↵
2 2 0 1 ↵
```↵
↵
**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$↵
↵
↵
<spoiler summary = "Solution">↵
↵
We can easily think of Brute Force Solution of getting mex for each index with a Complexity of $O(n^2)$ resulting in TLE. So For each index $i$, the $mex_i$ has to be determined in $O(1)$ or $O(\log{}{n})$. For this, we have to determine the mex of the whole array & for each index we will compare with this mex to get $mex_i$.↵
↵
Let, $mex = mex(a_1,a_2,\ldots,a_n)$. That means all numbers from $0$ to $mex-1$ remains in the array!↵
↵
Now for index $i$, if occurrence of $a_i$, $occ[a[i]]\gt 1$, then it does not affect the mex. So here $mex_i = mex$. But if $occ[a[i]]==1$, then its absence will change the mex if $mex\gt a[i]$. Then $mex_i = a[i]$. But if $mex\le a[i], mex_i=mex$. Ultimately, we get $mex_i=min(mex,a[i])$.↵
↵
**Complexity:** ↵
↵
$O(n)$ [If you use array for occurrence of each element of the array]↵
↵
$O(n\cdot \log{}{n})$ [If you use map for occurrence of each element of the array]↵
↵
</spoiler>↵
↵
↵
<spoiler summary="Code">↵
```c++↵
//﷽ [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;↵
}↵
```↵
↵
</spoiler>↵
↵
