I've found a solution in O(n^2) complexity which is as follows:

But is there any way in which I can reduce its time complexity?

This is the bin function

int bin(int n)
{
    int i = 0;
    while (n > 0)
    {
        if (n % 2 == 1)
            i  ;
        n = n / 2;
    }
    return i;
}

This is the code in main

for (int j = 0; j < n; j  )
                {
                    int ans = a[j];
                    for (int k = j   1; k < n; k  )
                    {
                        ans = ans ^ a[k];
                        if (bin(ans) % 2 == 0)
                        {
                            if (k - j   1 > final)
                            {
                                final = k - j   1;
                            }
                        }
                    }
                }

CodePudding user response：

Note two things:

1. Xor of two elements have even parity if and only if sum of their parities are even.

2. Xor of n elements equals to xor of n-1 elements xored with the nth.

If the sum of parities of all elements are even, then you are done. Array itself is the longest.

If not, then you can go through both end of the array at the same time looking for an odd parity byte. The sub-array leaving the first such element and the rest behind it is the longest. Done.

Note that there should be such element because otherwise sum will be even.

CodePudding user response：

A subarray with an even parity is a sequence of an arbitrary number of even numbers and an even number of odd numbers. If your array satisfies this, you are done (O(n)). Otherwise find an odd number that is closest to the front [or the back] and take the subarray past [or before] that position (O(n)).

This immediately gives you the proof that the subarray cannot be extended.