Help me in solving STBMEX problem

help
,
1

My issue

My code is not passing in some test cases . If anyone wondering why i pushed arr[0] after sorting it is to calculate the MEX until n ( when i hit the corner i will come out of the loop without cal the last subarray so pushed first element which definitetly smaller than the last element) . So could some one what is the wrong in my code

My code

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main() {
	// your code goes here
	int t ;
	cin >> t;
	while ( t > 0){
	    int n;
	    cin >> n;
	    vector <int> arr(n);
	    
	    for (int i = 0; i < n;i++)cin >> arr[i];
	    
	    sort(arr.begin(),arr.end());
	    arr.push_back(arr[0]);
	    if (arr[0] != 0)cout << arr[0] - 1 << endl;
	    else {
	        int mex = 1;
	        int count = 1;
	        int k = 0;
	        for (int i = 0; i < n;i++){
	            
	            if (arr[i] == arr[i+1])continue;
	            else if (arr[i] + 1 == arr[i+1]){
	                count ++ ;
	            }
	            else {
	                if (mex == 1)mex = count;
	                else {
	                    if (mex == count)k++;
	                }
	                count = 1;
	            }
	        }
	      
	           
	        if (mex == 1)cout << -1 << endl;
	        else cout << k << endl;
	    }
	    t--;
	}
	return 0;
}

Problem Link: STBMEX Problem - CodeChef

2

There are 3 problems with your code.
No.1: your mex-calculation is wrong.
Example Input:

1
5
0 1 3 4 5

your mex value: 4
correct mex value: 1
your output: 0
correct output: 1

You are trying to calculate the Mex inside the loop that calculates the solution. Don’t do that! Even if you could get it to work, it would not be faster, just harder to read, more prone to errors and harder to debug. First calculate the Mex, then do everything else.

No.2: you underestimate the amount of k-values
Example testcase:

8
0 1 2 4 5 6 7 8

In this case you have 2 consecutive subarrays: [0, 1, 2] and [4, 5, 6, 7, 8]. The second subarray is far bigger than your Mex, but if you choose k=6, then your total array will be [0, 0, 0, 0, 0, 0, 1, 2], which is valid.
your attempt:

if (mex == count)k++;

correct:

if (mex-1 <= count)k++;

No.3: you count the first consecutive sequence
Your code:

else cout << k << endl;

Correct code:

else cout << k-1 << endl;

Here is the full solution. I tried to change the least amount possible.

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main() {
	// your code goes here
	int t ;
	cin >> t;
	while ( t > 0){
	    int n;
	    cin >> n;
	    vector <int> arr(n);
	    
	    for (int i = 0; i < n;i++)cin >> arr[i];
	    
	    sort(arr.begin(),arr.end());
	    arr.push_back(arr[0]);
	    
	    //calculate mex
	    int mex = 0;
	    for (int i = 0; i < n; i++) if(arr[i] == mex) mex++;
	    
	    if (arr[0] != 0)cout << arr[0] - 1 << endl;
	    else {
	        /*int mex = 1;*/
	        int count = 1;
	        int k = 0;
	        for (int i = 0; i < n;i++){
	            
	            if (arr[i] == arr[i+1])continue;
	            else if (arr[i] + 1 == arr[i+1]){
	                count ++ ;
	            }
	            else {
	                if (mex == 1)/*mex = count*/;
	                else {
	                    if (mex-1 <= count)k++;
	                }
	                count = 1;
	            }
	        }
	      
	           
	        if (mex == 1)cout << -1 << endl;
	        else cout << k-1 << endl;
	    }
	    t--;
	}
	return 0;
}
3

Thanks for your effort !!! Really appreciate it !