Ignore it . I have not taken long long for sum upto m-1. got AC after contest.
Quick Question
- How do we validate assumptions ? For instance in an interview we can interviewer all questions.
For example in this question
- How do we assume it always input always starts from 1 ?
- How do we assume whether the input is always in increasing order ?
bro! you may try sorting initially
still this problem seems to have many loopholes in understanding the statements properly.
bro! in order to find desired solution
we assume
M : Smallest integer not present in chosen set(largest as demanded in problem) of elements
X : smallest positive integer not present in given sequence
if(X<M) then -1, coz irresspective whatever subset we choose X will always be resultant MEX and not M
e.g. {1, 2, 4, 6, 5 } ,X=3,M=5
if(X==M) cool the sequence is itself the largest subset with M as MEX
e.g. {2, 1, 5, 7} ,X=3,M=3
if(X>M) remove all occurrences of M , and we form largest subset from rest elements
e.g. { 5, 6, 3, 8 , 4, 3, 1, 2} X=7, M=3 largest subset will be { 5, 6, 8 , 4, 1, 2}
if you still feel some query still then post doubt more clearly
thanks!
@taran_1407
bro! in order to find desired solution
we assume
M : Smallest integer not present in chosen set(largest as demanded in problem) of elements
X : smallest positive integer not present in given sequence
if(X<M) then -1, coz irresspective whatever subset we choose X will always be resultant MEX and not M
e.g. {1, 2, 4, 6, 5 } ,X=3,M=5
if(X==M) cool the sequence is itself the largest subset with M as MEX
e.g. {2, 1, 5, 7} ,X=3,M=3
if(X>M) remove all occurrences of M , and we form largest subset from rest elements
e.g. { 5, 6, 3, 8 , 4, 3, 1, 2} X=7, M=3 largest subset will be { 5, 6, 8 , 4, 1, 2}
if you still feel some query still then post doubt more clearly
thanks!
bro
the thing you can do is make a subset that do not contain the elements you desire to remove
e.g. {1, 2, 3, 5, 4, 6 } , M=3,
then make subset {1, 2, 5, 4, 6 } not including 3 , its MEX is 3
1 Like
correct bro !
exhausted setter did not pay attention to displaying more test cases
-1 should be the output in this case?
totally agree mate. I felt the question was poorly constructed. Every time I came up with a code, I was contradicted by my own inference of the question.
got it thanks bro 
while(!s.empty() && s.top()==--m){
s.pop();
count++;
}
here if i am not wrong, then you have assumed that element less than m occur only once
but according to this misleading problem ,
element less than m can occur any no of times in the given sequence
try this instead
while(!s.empty() && s.top()<m){
s.pop();
count++;
}
still the code need correction and i.e.
pls ensure that all element less than m occurs at least 1 time in the given sequence else m will not be the MEX. i used arrays to do this
for(int i=1;i<=m-1;i++)
{
if(binary_search(arr,arr+n,i))
{
flag++;
}
}
if(flag!=m-1)
{
cout<<"-1"<<endl;
}
# cook your dish here
a=int(input())
for i in range(a):
x=list(map(int, input().split()))
f=list(map(int, input().split()))
f.sort()
MEX=0
for i in list(range(1, max(f)+1)):
if i not in f:
MEX+=i
break
if MEX==x[1]:
print(len(f))
elif MEX<x[1]:
print(-1)
else:
for i in range(len(f)):
if f[i]==x[1]:
f.pop(i)
print(len(f))
Why am I getting a runtime error here? Please tell me the changes.See this,
if A[]={1, 2, 4, 3, 6, 5}
M=6
then what will a correct code return ?
-1 : logically because there is no MEX in the given sequence, therefore X not exists
so we cannot compare X,N
problem does not account for this case ,
what should our code return in this particular e.g. according to editorial explanation
According to the statement: " the smallest positive integer which does not occur among the chosen element. "
can someone please tell what is the MEX for the array: [1,2,3,4,5,6]
-> If the MEX is ā7ā, then what is the significance of the statement āamong the chosen elementsā. It should have been something like āamong the +ve integersā.
-> If the MEX is āNONEā, by the exact meaning of the statement āamong the chosen elementsā, then the whole editorial is contradictory.
Editorial : MEX of a sequence is the smallest positive integer not present in the sequence.
Problem:MEX, i.e. the smallest positive integer which does not occur among the chosen elements.
These two statements are same for e.g. if you you choose set of no [45,46,47] only then also the mex will be 1 (one may or may not be present in the given sequence).
So, in the end you need all such integers such that all values less than m should be present and m should not be present in the given sequence (selected subset). 
So, we have to start every sequence by assuming it starts with 1.
like in [4,7,8,9,10] MEX = 1 and if m=6 or 5 then answer will be -1.
I can see only one problem in the solutionā¦ Since repeated elements are allowed, itās not guaranteed that the sum of elements smaller than m present in the array is m * (m - 1)/2. We have to check it using either a set or hashtable.
Can someone help me figure out the test cases??
3
4 3
1 2 4 5
6 3
1 2 4 6 7 8
6 3
1 4 5 6 7 8
According to me output should should be : 4 6 1
Am I right or wrong?
In the test case provided by you - MEX(i.e X) exists and is equal to 7 and the code will return or print 5.
You can check my solution here
I hope it helps you 
1 Like