Subarray Removal | codechef solution

Rajnish Tripathi 04:30

 Problem:-

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

1. Select any � and � such that (1≤�<�≤∣�∣)2. Add ��⊕��+1⊕…⊕�� to his score (Here, ⊕ denotes the bitwise XOR operation)3. Remove the subarray ��…� 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,…,�� denoting the array �.

Output Format

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

Constraints

  • 1≤�≤105
  • 1≤�≤105
  • ��∈{0,1}
  • The sum of � over all test cases won't exceed 2⋅105.

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:

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

Total score =1+1=2

Test Case 2: We can perform the following move:

  • �=[1,1,1]. Select �=1 and �=3 and remove subarray [1,1,1]. � becomes [].

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:-

Companies interview:-

Full C course:-    

Key points:-

Cracking the coding interview:-

 Array and string:-

Tree and graph:-

Hackerearth Problems:-

Hackerrank Problems:-

Data structure:-

 MCQs:-

Tags: