This is the confusing part, MEX is the smallest positive integer which doesn’t occur in the set, hence, the answer will be -1. Because MEX of 4 7 8 is 1.
To clarify, look at the code:
int mex=1;
while(s.count(mex)){
mex++;
}
The answer is mex when the while loop breaks. So you take a set and start checking if 1 occurs, then you proceed to 2,3,4 and so on. until you find the one element that doesn’t occur, this shall be considered as MEX of the given Set.
The statement was confusing and a test case explaining the whole scenario would’ve gone a long way for us.
-1
You understood the problem wrong.
7 is also not present in the sequence.
1 Like
My day is ruined and my disappointment is immeasurable.
2 Likes
ok now I got it. Thanks man
Such poorly explained problem. They should have clarified that we need to choose subsequence of array rather than subarray , it was just written choose largest no. of elements (In what) . A problem should be easily understandable . But everything has a learning next time whenever there is written choose largest number , I will assume it to be subsequence .@rezwanarefin01 @raja1999
2 Likes
Right…this also happened to me.
Question was poorly defined.
Question says
Chef has a sequence of positive integers A1,A2,…,ANA1,A2,…,AN. He wants to choose some elements of this sequence (possibly none or all of them) and compute their
MEX, i.e. the smallest positive integer which does not occur among the chosen elements
If we go by this logic than for input
1
9 8
1 2 3 5 6 7 9 10 11
The output should be [5,6,7,9,10,11] i.e 6. But according to the solution provided it is different.
Poorly defined question
Yeah I got it. Thanks man
@taran_1407
There should be atleast 2-3 examples with proper explanations for each example. Also, the question description was really bad.
Checkout Leetcode or Hackerrank. They give plenty of examples with proper explanations to each one of the example.
Please take this as a constructive criticism. Thanks.
2 Likes
I agree with you totally Brother.It Took me 1 Hour to interpret what the question is asking to do.Problem Statement was a bit confusing.
I also asked in comments of 2nd problem but no one replied me.
Thanks @adarsh08x for the reply.
E.g.
1
6 6
4 5 7 8 9 10
According to your post following test case should return the total length of the array.
I have looked at the editorial code which is written in Java. But the output is returned as -1.
yes it will return -1 because 1,2,3, are not present in the in the array
just add 1,2,3 then it will return the whole length
my solution
/* package codechef; // don’t place package name! */
import java.util.;
import java.lang.;
import java.io.*;
/* Name of the class has to be “Main” only if the class is public. */
class Codechef
{
public static void main (String[] args) throws java.lang.Exception
{
Scanner sc=new Scanner(System.in);
int t=sc.nextInt();
for(int i=0;i<t;i=i+1)
{
int n=sc.nextInt();
int m=sc.nextInt();
int array[]=new int[n];
for(int j=0;j<n;j=j+1)
{
array[j]=sc.nextInt();
}
Arrays.sort(array);
//Find Mex
int x=1;
for(int j=0;j<n;j=j+1)
{
if(x<array[j])
{
break;
}
x=array[j]+1;
}
//System.out.println(x);
if(x==m)
{
System.out.println(n);
}
else if(x<m)
{
System.out.println("−1");
}
else if(x>m)
{
int count=0;
for(int j=0;j<n;j=j+1)
{
if(array[j]==m)
count=count+1;
}
System.out.println(n-count);
}
}
}
}
What is wrong in this code? It is giving WA.
Can anyone please help me find a mistake with my code. Have spent hours but couldn’t get. All the manual test cases which I could think of gets passed but Codechef says Wrong Answer.
Pls help guys… https://www.codechef.com/viewsolution/34646376
Worst explanation of the question i have ever seen till now.
1 Like
thanks for your time bro… actually m*(m-1)/2 will be of long long type and i had taken int. it got AC now doing this. Repeated element I had taken care by counting only 1 instance of no. < m by using map. once again, thanks for your time. let me know if I can return the favor if its feasible for me.
1 Like