In this HackerEarth Divide arrays problem solution You are given an array A of N integers. Find the smallest index i (1 <= i <= N – 1) such that:
mex(A[1],A[2],…,A[i]) = mex(A[i+1],A[i+2],…,A[N])
If no such index exists, print -1.
HackerEarth Divide arrays problem solution.
#include<bits/stdc++.h>
#define int long long int
using namespace std;
void solve(){
int n;
cin >> n;
assert(1 <= n and n <= 100000);
set<int>s;
for(int i = 0 ; i <= n ; i++) s.insert(i);
int a[n+1];
for(int i = 1 ; i <= n ; i++){
cin >> a[i];
assert(0 <= a[i] and a[i] <= 100000);
}
int prefmex[n + 1];
int sufmex[n + 1];
for(int i = 1 ; i <= n ; i++){
if(s.find(a[i]) != s.end())
s.erase(a[i]);
prefmex[i] = *(s.begin());
}
s.clear();
for(int i = 0 ; i <= n ; i++) s.insert(i);
for(int i = n ; i >= 1 ; i--){
if(s.find(a[i]) != s.end())
s.erase(a[i]);
sufmex[i] = *(s.begin());
}
int ans = -1;
for(int i = 1 ; i <= n - 1 ; i++){
if(prefmex[i] == sufmex[i + 1])
{
cout << i << endl;
return;
}
}
cout << -1 << endl;
}
signed main(){
int t;
cin >> t;
assert(1 <= t and t <= 10);
while(t--){
solve();
}
}
Second solution
MAX_N = int(1e5 + 14)
t = int(input())
while t > 0:
t -= 1
n = int(input())
a = list(map(int, input().split()))
mark = [False] * MAX_N
mex = 0
pre = []
for x in a:
mark[x] = True
while mark[mex]:
mex += 1
pre += [mex]
mark = [False] * MAX_N
mex = 0
ans = -1
for i in range(n - 1, 0, -1):
mark[a[i]] = True
while mark[mex]:
mex += 1
if mex == pre[i - 1]:
ans = i
print(ans)