# Subarray Removal | codechef solution

## Problem:-

Chef has a binary array $�$ of length $�$. In one operation, Chef does the following:

1. Select any $�$ and $�$ such that $\left(1\le �<�\le \mathrm{\mid }�\mathrm{\mid }\right)$$\phantom{\rule{0ex}{0ex}}$2. Add ${�}_{�}\oplus {�}_{�+1}\oplus \dots \oplus {�}_{�}$ to his score (Here, $\oplus$ denotes the bitwise XOR operation)$\phantom{\rule{0ex}{0ex}}$3. Remove the subarray ${�}_{�\dots �}$ from $�$

Determine the maximum score Chef can get after performing the above operation any number of times.

### Input Format

• The first line contains a single integer $�$ — the number of test cases. Then the test cases follow.
• The first line of each test case contains an integer $�$ — the size of the array $�$.
• The second line of each test case contains $�$ space-separated integers ${�}_{1},{�}_{2},\dots ,{�}_{�}$ denoting the array $�$.

### Output Format

For each test case, output the maximum score Chef can get.

### Constraints

• $1\le �\le 1{0}^{5}$
• $1\le �\le 1{0}^{5}$
• ${�}_{�}\in \left\{0,1\right\}$
• The sum of $�$ over all test cases won't exceed $2\cdot 1{0}^{5}$.

### Sample 1:

Input
Output
3
5
1 0 0 0 1
3
1 1 1
3
0 0 0

2
1
0


### Explanation:

Test Case 1: We can perform the following moves:

• $�=\left[1,0,0,0,1\right]$. Select $�=1$ and $�=3$ and remove subarray $\left[1,0,0\right]$$�$ becomes $\left[0,1\right]$.
• $�=\left[0,1\right]$. Select $�=1$ and $�=2$ and remove subarray $\left[0,1\right]$$�$ becomes $\left[\right]$.

Total score $=1+1=2$

Test Case 2: We can perform the following move:

• $�=\left[1,1,1\right]$. Select $�=1$ and $�=3$ and remove subarray $\left[1,1,1\right]$$�$ becomes $\left[\right]$.

Total score $=1$

#include <algorithm>
#include <iostream>

static void testcase() {
unsigned N;
std::cin >> N;
int one = 0;
int zero = 0;
while(N--) {
unsigned Ai;
std::cin >> Ai;
one += Ai == 1;
zero += Ai == 0;
}
std::cout << (std::min(one, zero) + std::max(0, one - zero) / 3) << '\n';
}

int main() {
std::ios_base::sync_with_stdio(false);
std::cin.tie(nullptr);
unsigned T;
std::cin >> T;
while(T--)
testcase();
}

### Recommended Post :-

HCL Coding Questions:-

Capgemini Coding Questions:-
iMocha coding Questions:-
Tech Mahindra coding questions:-
Unthinkable Solutions coding questions:-