HackerEarth Divide arrays problem solution

YASH PAL, 31 July 202411 February 2026

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

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)

coding problems solutions HackerEarth HackerEarth

Leave a Reply