# PROBLEM LINK:

Contest Division 1

Contest Division 2

Contest Division 3

Contest Division 4

**Setter:** Jeevan Jyot Singh

**Tester:** Takuki Kurokawa

**Editorialist:** Kanhaiya Mohan

# DIFFICULTY:

Simple

# PREREQUISITES:

# PROBLEM:

Chef has an array A of length N. Chef wants to select some **disjoint, non-empty** subarrays from A such that:

- The mex of each of the selected subarray is the same.

Note that the selected subarrays **need not cover** all the elements of the array.

Chef wants to select the maximum number of disjoint, non-empty subarrays that satisfy the above condition. Can you help him to do so?

# EXPLANATION:

## Hint 1

Think of subarrays of length 1.

## Hint 2

The MEX of a subarray of length 1 is either 0 (if the element is non-zero) or 1 (if the element is 0).

## Solution

We consider all the elements of the array as disjoint subarrays. There are two possible cases for each subarray:

- The subarray is element 0. In this case, MEX of the subarray is 1.
- The subarray is a non-zero element. In this case, MEX of the subarray is 0.

Let the count of zeros in the array A of length N be X. This means that there are (N-X) non-zero elements in the array.

Thus, the total number of disjoint subarrays with MEX equal to 1 are X. Similarly, the total number of disjoint subarrays with MEX equal to 0 are (N-X).

Since we want maximum subarrays with the same MEX, our answer is max(X, N-X).

Note that we cannot have a greater answer in any other selection of subarrays since the total number of disjoint subarrays would reduce.

# TIME COMPLEXITY:

The time complexity is O(N) per test case.

# SOLUTION:

## Setter's Solution

```
#include<bits/stdc++.h>
using namespace std;
void solve() {
int n;
cin >> n;
int ans = 0;
for (int i = 0; i < n; i++) {
int x; cin >> x;
ans += (x == 0);
}
cout << max(ans, n - ans) << '\n';
}
int main() {
int t;
cin >> t;
while (t--) {
solve();
}
return 0;
}
```

## Tester's Solution

```
#include <bits/stdc++.h>
using namespace std;
int main() {
int tt;
cin >> tt;
while (tt--) {
int n;
cin >> n;
vector<int> a(n);
for (int i = 0; i < n; i++) {
cin >> a[i];
}
int zeros = (int) count(a.begin(), a.end(), 0);
cout << max(n - zeros, zeros) << endl;
}
return 0;
}
```

## Editorialist's Solution

```
#include <iostream>
using namespace std;
int main() {
int t;
cin>>t;
while(t--){
int n;
cin>>n;
int zero_count = 0;
int nonzero_count = 0;
for(int i = 0; i<n; i++){
int x;
cin>>x;
if(x==0) zero_count++;
else nonzero_count++;
}
cout<<max(nonzero_count, zero_count)<<endl;
}
return 0;
}
```