Header Ads Widget

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

  • 1105
  • 1105
  • {0,1}
  • The sum of  over all test cases won't exceed 2105.

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