 # MEXPROB - Editorial

Dude Your Time Complexity is N^2logN^2 try reducing it to O(N^2) !!

Spoiler

Instead of Taking B array of size 100000000 Take ‘Count’ array of size N+1 since MEX of the array can be [0, N] so each time u get a MEX, update the count of MEX
Now you have count of each number .i. e. how many times each number is MEX now you can just iterate on count array and find kth small MEX;

1 Like

MEX for a= is 0
For calculating MEX: take an array of size of N+1 and update all elements to 0

Summary
``````   int ans[n+1]={0};
for(int i=0;i<n;i++)
{
int b[N+1]={0},mex=0;
for(int j=i;j<n;j++)
{
b[a[j]]=1;
while(b[mex])
{
mex++;
}
ans[mex]++;
}

``````

Now each time we update count of mex since mex variable has the MEX value

1 Like

https://www.codechef.com/viewsolution/52305961

Why this is not passing subtask 1?

could you share any youtube video or detailed description for this mex calculating program? i still didn’t get it.

1 Like
1 Like

sir,what is the use of a[r] in cnt[a[r]]++,i means what is the value of a[r] in cnt[a[r]] in loop,as we dont assign any value in this vector a[maxn]
replie kindly m doubt

can you please elaborate I don’t get you!

cnt array is used to keep track number of times a number is MEX

Solution: 52856209 | CodeChef

can some 1 plz tell me why code is giving me tle for one test case adn wa for other?