Physical Address
304 North Cardinal St.
Dorchester Center, MA 02124
Stable Mex CodeChef Solution
Problem -Stable Mex CodeChef Solution
This website is dedicated for CodeChef solution where we will publish right solution of all your favourite CodeChef problems along with detailed explanatory of different competitive programming concepts and languages.
<<Previous CodeChef Problem Next Codechef Problem>>
Stable Mex CodeChef Solution in C++17
#include <bits/stdc++.h>
using namespace std;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
void solve() {
int n;
cin >> n;
vector<int> a(n);
for (int i = 0; i < n; i++) cin >> a[i];
sort(a.begin(), a.end());
a.erase(unique(a.begin(), a.end()), a.end());
int mex = a.size();
for (int i = 0; i < a.size(); i++) if (a[i] != i) {
mex = i;
break;
}
if (mex == 0) {
cout << a[0] - 1 << '\n';
return;
}
if (mex == 1) {
cout << "-1\n";
return;
}
a.push_back(1e9 + 5);
int ans = 0;
mex--;
for (int i = mex + 1; i < a.size(); i++)
if (i + mex < a.size() && a[i + mex] > a[i] + mex && a[i + mex - 1] == a[i] + mex - 1) ans++;
cout << ans << '\n';
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(0);
int t = 1;
// gen_primes();
// gen_factorials((int)5e5 + 5);
// cout << fixed << setprecision(6);
cin >> t;
for (int te = 0; t--;){
// cout << "Case #" << ++te << ": ";
solve();
}
}Stable Mex CodeChef Solution in C++14
#include<bits/stdc++.h>
using namespace std;
#define lli long long int
#define pii pair<int,int>
#define vi vector<int>
#define vvi vector<vector<int>>
#define vpi vector<pair<int,int>>
#define pb push_back
#define pf push_front
#define ff first
#define ss second
#define rep(start,n) for(int i = start; i < n; ++ i)
#define mod 1000000007
#define fix fixed<<setprecision(10)
int findMex(int arr[], int n){
int k = 0;
int i = 0;
if(n==1 and arr[0]==0)
return 0;
while(i<n){
if(k==arr[i]){
i++;
k++;
}
else i++;
}
return k;
}
int removeDuplicates(int arr[], int n)
{
// Return, if array is empty or contains a single
// element
if (n == 0 || n == 1)
return n;
int temp[n];
// Start traversing elements
int j = 0;
// If current element is not equal to next element
// then store that current element
for (int i = 0; i < n - 1; i++)
if (arr[i] != arr[i + 1])
temp[j++] = arr[i];
// Store the last element as whether it is unique or
// repeated, it hasn't stored previously
temp[j++] = arr[n - 1];
// Modify original array
for (int i = 0; i < j; i++)
arr[i] = temp[i];
return j;
}
void solve() {
int n; cin>>n;
int arr[n];
map<int,int>mp;
for(int i=0; i<n; i++) {
cin>>arr[i];
mp[arr[i]]=1;
}
sort(arr, arr+n);
n = removeDuplicates(arr, n);
int mex = findMex(arr, n);
// cout<<mex;
if(mex==0) cout<<arr[0]-1<<endl;
else if(mex==1) cout<<-1<<endl;
else{
int i = mex;
int x = arr[mex-1] - arr[0]-1;
// cout<<x<<" ";
int j = mex+x;
int c = 0;
while(i<n and j<n){
if(mp[arr[i]+mex-1]==0){
if((arr[j]-arr[i])==x){
c++;
}
}
i++;
j++;
}
cout<<c<<endl;
return;
}
}
int main() {
// ios_base::sync_with_stdio(false);
// cin.tie(NULL);
// cout.tie(NULL);
int T = 1;
cin >> T;
for (int t = 1; t <= T; t++) {
// cout << "Case #" << t << ": ";
solve();
}
return 0;
}Stable Mex CodeChef Solution in PYTH 3
# cook your dish here
import math
import bisect
for i in range(int(input())):
n=int(input())
# N,K,L=map(int,input().split())
A=[int(k) for k in input().split()]
# s=input()
# b=sorted(A)
b=list(set(A))
b.sort()
d=len(b)
mex=0
k=0
while k<d:
if b[k]!=k:
mex=k
break
else:
if k==(d-1):
mex=d
k+=1
if mex==0:
c=b[0]
print(c-1)
elif mex==1:
print(-1)
elif mex==2:
c=0
for k in range(1,d):
if b[k]<mex:
pass
else:
if b[k]-b[k-1]==1:
c+=1
print(d-2-c)
else:
c=0
count=1
y=0
k=0
n=d
while(k<n):
if b[k]<mex:
k+=1
else:
if b[k]-b[k-1]==1:
if y==0:
y=1
count+=1
else:
count+=1
if k==(n-1):
if y==1 and count>=mex-1:
c+=1
k+=1
else:
k+=1
else:
k+=1
else:
if y==0:
k+=1
elif y==1 and count>=mex-1 :
c+=1
count=1
y=0
k+=1
else:
y=0
count=1
k+=1
# elif b[k]>mex and b[k]-b[k-1]==1 and b[k-1]>mex:
# count+=1
# k+=1
# else:
# count=1
# k+=1
# if count==mex:
# if k<n:
# if b[k]-b[k-1]>1:
# c+=1
# k+=2
# else:
# count=1
# k+=1
# # k+=1
print(c)
Stable Mex CodeChef Solution in C
#include<stdio.h>
#include<math.h>
#include<string.h>
#define M 1000005
#define A 200005
typedef long long (ll);
char s[105],t[5];
ll z[A];
void merge(ll arr[],ll l,ll m,ll r)
{
ll i,j,k,n1,n2;
n1=m-l+1;
n2=r-m;
ll L[n1],R[n2];
for(i=0;i<n1;i++)
L[i]=arr[l+i];
for(j=0;j<n2;j++)
R[j]=arr[m+1+j];
i=j=0;
k=l;
while(i<n1&&j<n2)
{
if(L[i]<R[j])
arr[k++]=L[i++];
else
arr[k++]=R[j++];
}
while(i<n1)
arr[k++]=L[i++];
while(j<n2)
arr[k++]=R[j++];
}
void sort(ll arr[],ll l,ll r)
{
if(l<r)
{
ll m=l+(r-l)/2;
sort(arr,l,m);
sort(arr,m+1,r);
merge(arr,l,m,r);
}
}
int main()
{
ll a,b,c,d,e,f,g,h,i,j,k,l,m,n,o;
double p;
scanf("%lli",&a);
for(;a;a--)
{
scanf("%lli",&b);
for(c=0;c<b;c++){
scanf("%lli",&z[c]);
}
sort(z,0,b-1);
for(c=d=0;c<b;c++){
if(z[c]==d)d++;
}
if(z[0]>0)n=z[0]-1;
else if(d==1)n=-1;
else {
n=e=h=0;
for(c=b-1;c>=0;c--){
if(e==0){
f=z[c]-1;
h=1;
e=1;
}
else{
if(z[c]==f+1){}
else if(z[c]==f){
h++;
if(h==d)n++;
f--;
}
else{
f=z[c]-1;
if(h==d-1)n++;
h=1;
}
}
if(z[c]<d)break;
}
}
printf("%lli\n",n);
}
}Stable Mex CodeChef Solution in JAVA
/* 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
{
Input1 aa;
public int calcMex(int ar[],int n){
int i=0;
int c=0;
while(i<n)
{
if(ar[i]>c)
return c;
c++;
i++;
}
return c;
}
public void calc() throws Exception{
int n=ni();
int ar[]=new int[n];
int i,j,c;
for(i=0;i<n;i++)
{
ar[i]=ni();
}
Arrays.sort(ar);
i=0;
j=1;
while(j<n){
while(j<n && ar[j]==ar[i])
j++;
if(j>=n)
break;
i++;
ar[i]=ar[j];
j++;
}
n=i+1;
int mex=calcMex(ar,n);
int ans=0;
if(mex==0){
ans=ar[0]-1;
}
else if(mex==1){
ans=-1;
}
else {
i=0;
j=1;
c=1;
ans=0;
while(j<n){
while(j<n && (ar[j]-1)==ar[j-1]){
c++;
j++;
}
if(c>=(mex-1))
ans+=1;
i=j;
if(j>=n)
break;
j++;
c=1;
}
ans-=1;
if(i<n && c>=(mex-1))
ans+=1;
}
System.out.println(ans);
}
public void run() throws Exception{
aa=new Input1();
int t=ni();
while(t-->0)
{
calc();
}
}
public static void main (String[] args) throws java.lang.Exception
{
// your code goes here
try{
new Codechef().run();
}
catch(Exception ee){
}
}
public int ni() throws Exception{
return Integer.parseInt(aa.next());
}
class Input1{
BufferedReader br;
StringTokenizer str;
public Input1(){
br=new BufferedReader(new InputStreamReader(System.in));
}
public String next() throws Exception{
while(str==null || !str.hasMoreTokens()){
str=new StringTokenizer(br.readLine());
}
return str.nextToken();
}
}
}Stable Mex CodeChef Solution in PYPY 3
for _ in range(int(input())):
n=int(input())
l=list(map(int,input().split()))
l=list(set(l))
n=len(l)
l.sort()
found,mex,ans,cnt=False,n,0,0
for i in range(n):
if(not found):
if(i!=l[i]):
mex,found,cnt=i,True,1
else:
if(l[i]-l[i-1]==1):
cnt=cnt+1
else:
if(cnt>=mex-1):
ans=ans+1
cnt=1
ans=ans+1 if cnt>=mex-1 else ans
ans=-1 if mex==1 else ans
ans=l[0]-1 if mex==0 else ans
print(ans)Stable Mex CodeChef Solution in C#
using System;
using System.Linq;
using System.Collections.Generic;
using System.Text.RegularExpressions;
using System.Text;
using System.Numerics;
public class Test
{
public static int GetInt() => int.Parse(Console.ReadLine());
public static long GetLong() => long.Parse(Console.ReadLine());
public static int[] GetIntArray() => Console.ReadLine().Trim().Split(' ').Select(int.Parse).ToArray();
public static long[] GetLongArray() => Console.ReadLine().Trim().Split(' ').Select(long.Parse).ToArray();
public static int Gcd(int a, int b) => b == 0 ? a : Gcd(b, a%b);
public static int Gcd(int[] n) => n.Aggregate((a,b) => Gcd(a,b));
public static void Main()
{
var t=GetInt(); for(int i = 0; i<t; i++) { Solve(); }
// Solve();
}
public static int GetMex(int[] a, int upperBound)
{
bool[] t = new bool[upperBound];
foreach(int v in a)
{
if(v>-1 && v < upperBound)
{
t[v] = true;
}
}
for(int i=0; i<upperBound; i++)
{
if(!t[i])
return i;
}
return -1;
}
public static void Solve()
{
int n = GetInt();
var a = GetIntArray().Distinct().ToArray();
Array.Sort(a);
//find mex
int mex = GetMex(a, 100100);
if(mex == 1)
{
Console.WriteLine("-1");
return;
}
else if(mex == 0)
{
Console.WriteLine(a[0]-1);
return;
}
//max > 1
var sizes = a
.Select((v,i) => v-i)
.GroupBy(_ => _)
.Select(_ => _.Count())
.ToArray();
int ans = sizes.Count(_ => _>= mex - 1)-1;
Console.WriteLine(ans);
}
}Stable Mex CodeChef Solution Review:
In our experience, we suggest you solve this Stable Mex CodeChef Solution and gain some new skills from Professionals completely free and we assure you will be worth it.
If you are stuck anywhere between any coding problem, just visit Queslers to get the Stable Mex CodeChef Solution.
Conclusion:
I hope this Stable Mex CodeChef Solution would be useful for you to learn something new from this problem. If it helped you then don’t forget to bookmark our site for more Coding Solutions.
This Problem is intended for audiences of all experiences who are interested in learning about Programming Language in a business context; there are no prerequisites.
Keep Learning!
