Magical Subarrays

editorial
, , ,
1

Can someone explain how to solve the question below, Much appreciated!

Given an integer arr[] of size n, your task is to count the number of magical subarrays in the arr.

Here any subarray arr[l…r] is considered to be magical if it satisfies the magical condition.

it should contain an even number(non zero) of odd numbers

More Formally the count of odd numbers in the subarray should be even and should be greater than 0

#TestCase 1;
Input:
n=4
arr[]={2,1,2,3}

output:2
the magical subarrays are: {2,1,2,3} , {1,2,3}

#Testcase 2
n=6
arr[]={1,2,5,2,3,7}

output:7
the magical subarrays are:{1,2,5}, {1,2,5,2}, {2,5,2,3}, {5,2,3}, {2,3,7}, {3,7}, {1,2,5,2,3,7}

1 Like
2

Consider making the array a represent the number of odd numbers between every two even numbers (including the leftmost and rightmost continuous odd numbers).

For example, \{2,1,2,3\} will be converted to \{0,1,1\} and \{1,2,5,2,3,7\} will be converted to \{1,1,2\}.

then \text{answer=}\sum\limits_{i=1}^n\sum\limits_{j=i+1}^n[i≡j\mod2](a_i+1)(a_j+1)

Then only need to do perfix sum once for odd numbers and once for even numbers.

3

If a subarray contains even number of odd elements then the sum of the subarray must be even as well. Do note that 0 odd numbers will also give even sum.
So question can be rephrased as “Find the number subarrays having even sum”, and subtract the number of subarrays having only even numbers/ 0 odd from it.

For finding even sum subarrays there’s a classical method involving prefix sum. The idea is that as you traverse the array you check whether the subarray ending at ith index had even or odd prefix sum. Keep counter for number of both of such arrays. If you get an even prefix sum subarray at ith index then you can subtract any of previously found such subarrays to get even sum. Similarly for odd sum you can subtract any previous odd sum subarray to get even sum.
A little thing to note here is that you can technically subtract nothing (empty subarray/ 0 prefix sum) from an even prefix sum subarray as well. So start the count of even prefix subarrays with 1.

For 0 odd numbers you can traverse the array and keep track of continuous even numbers streak and whenever the streak resets (due to an odd number or end of array) use the formula n * (n +1) / 2 to get number of such subarrays, where n is the length of the streak.