Subarray Removal

I took this Problem yesterday but there was some bug in my code, so today I started from square one and tried to understand what could be the hidden bug in my logic. Apparently I was doing the correct thing although in the wrong order, I thought about a case today which would have caused a problem for my previous approach. Like if we take the example case as, 111000, then my previous implementation would give answer to be 1, but this is wrong because we can make a score of 3 from this case.

This was the main problem in my implementation, that is I was considering both the scenarios( the ways in which we can score by the use of XOR operator ) at once, like getting score from 3 ones and from 2 different bits( 01 or 10 ). 

But, what I should have done is to first take all the scores that I we can score from 2 length subarrays and ignoring the 3 length ones, because of the same reason that these 3 1's can be used in a more optimal way, by pairing them with 0's, and if that is not possible so after that we can look for the next type of score pattern that is looking for 3 1's.

Well, I got a While in my code too... ;)

Problem Statement:-

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

1. Select any $�$ and $�$ such that $(1\le �<�\le \mathrm{\mid }�\mathrm{\mid })$$$2. Add ${�}_{�}\oplus {�}_{�+1}\oplus \dots \oplus {�}_{�}$ to his score (Here, $\oplus$ denotes the bitwise XOR operation)$$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 10^5$
• $1\le �\le 10^5$
• ${�}_{�}\in \{0,1\}$
• The sum of $�$ over all test cases won't exceed $2\cdot 10^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:

• $�=[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$

Code Implementation:-

for _ in range(int(input())):

    n=int(input())

    # Taking the input as a string so that we have less work

    # to do instead of maintaining an array

    nums="".join(list(input().split()))

    # nums="".join(nums)

    score=0

    while(True):

        change=False

        for i in range(len(nums)):

            # If we can check the next elem, check for different terms,

            # if yes, then we add to score

            if((i+1)<len(nums) and nums[i]!=nums[i+1]):

                score+=1

                nums=nums[0:i]+nums[i+2:]

                change=True

               

                ''' The Below break statement caused a problem by

                    increasing the overall TC by 1.2 secs '''

                # break

        if(change==False):

            break

       

    # Now till here we don't have any 2 sized scorables left in the array...

    # Now we will check for 1s left in the array if any, if we don't

    # get any change then we will just exit loop

    while(True):

        change=False

        for i in range(len(nums)):

            # Same for the case of 3 1s

            if((i+2)<len(nums) and nums[i]=='1' and nums[i+1]=='1' and nums[i+2]=='1'):

                score+=1  

                nums=nums[0:i]+nums[i+3:]

                change=True

        # If there won't be any change then we will just get out of

        # the loop, that's it

        if(change==False):

            break

    print(score)

Explanation:-

Simply, I am taking input as a string and not as an array because I thought that would be more efficient. Then, we go 

inside the First While loop, here I am checking for the 2 different bits in the whole string, I will keep removing them and keep traversing the array as long as there are any left, otherwise when there won't be any 2 different bits left, then will just break out of the loop( this is done by the use of the change variable which is initially set to False, and if some change occurs so change will become True ). Now. after this loop I am sure there isn't any 2 sized substrings left to score, so there can be only some 3 sized strs with all 1's. To search for them we go inside the 2nd while loop. For this loop too if there are any triplets of 1, so increase the score and remove them else just get out of loop and print score. Note: I am making sure that when I dynamically change the string it doesn't affect the flow of loop by taking len(nums) everywhere instead of using n(bcz size will be changing). And I am making sure that I don't make any Index error by first checking if I can access the i+1 index of the i+1 and i+2 indices or not, then only I am checking the other conditions.