Is input array always Sorted ???
@rezwanarefin01 what will happen if A contains any element more than 1 copy then set st will insert anyone of them .it will decrease the count of inserted element so why its not giving weightage on submission.
Only in case of MEX==M
what you have mentioned above the question is judging like that only ???
i don’t understand why you have checks for a[i] > m ?
things that matter in the problems are … first that there should be all values in range [1,m-1] available in array…
if first condition is true print (size of array - count of m’s in array)
in the setters solution ,it will make more sense if the mex should be initialized by the first ele of the set instead of 1…
1 Like
Please take a minute to see my code.
My whole day is gone in WA for this question. I dont know whats wrong in this CodeChef: Practical coding for everyone
i believe you code’s logic is incorrect.
you are finding tha maximumvalue out of first N number which is not available in the array?
and then checking if maximum is == m?
you didn’t understand the concept of MEX, it is minimum excluded, not maximal excluded.
that means MEX of following arrays are :
[2,3,5,9,8,10,12,13,14] = 1 not 9.
[1,2,3,5,6,7,8,9,15,16,17] = 4 not 10.
my code is correct its giving 1 as mex and not 9
i am using break so if we first encounter any number which is missing thats mex and break
see my code again plzz.
1 Like
did u found out anything that i should change in my code??
i believe you method of finding MEX was wrong ←
as you were assuming that array is going to be sorted i guess and array will not contain dublicate values.
CodeChef: Practical coding for everyone ← i modified that part and got AC.
Can we not think of Peageonhole principle for this problem ?
As is N<=10^5 , So possible MEX can be between 1 to 100001 . If m>100001, we can simply output -1
Else we can have a frequency array of size 100002 (index from 0 to 100001), in this we can save frequencies of the elements.
If the m>100001, we can traverse the freq array and check that all elements which are between 1 to m-1 should be present ,
if (they are all present then ans will be the sum of no. of elements between 1 to m-1 plus the sum of no. of elements greater than m)
else ans should be -1
Time Complexity - O(n)
Space - same
Please review my approach. Is it right ? Or tell me some counter test case. Thanks in advance !!