Count Subarrays with Same Even and Odd Elements

Suppose you have given an integer array of N size. As there are numbers, numbers are odd or even. The problem statement is count subarray with the same even and odd elements or finds out the count of sub-arrays that has an equal number of even and odd integers.

Table of Contents

Example

Input

arr[] = {2, 5, 1, 6};

Output

Explanation

As there are ⇒ {2, 5}, {1, 6}, {2, 5, 1, 6}

Input

arr[] = {2,3,4,5,1,6}

Output

Algorithm

Declare two arrays, positiveNum and negativeNum of size n+1.
Set count and output to 0, and set positiveNum[0] to 1.
Traverse the array from i=0, to i<n(length of the array).
1. Check if bitwise and operation arr[i] & 1 is equal to 1,
  1. If true, then increase the count by 1.
2. Else, decrease the count by 1.
3. If the count is less than 0, then add the output to negativeNum[-count] and store it to output.
4. Else, add the output to positiveNum[count] and store it to output.
Return output.

Explanation

We will make the two hash arrays, one for storing the positive difference, and one is for negative differences. With differences, we mean to say, we are going to find out the differences between the frequencies of odd and even integers. Setting the output to 0, in this, we will update our answer, count to 0, this will maintain the difference count. After declared two hash arrays, set the positive one to 1, positiveNum[0]=1.

We will traverse the array, and check if it is an odd value or positive, for this we will use Bitwise AND operator, if use the AND operator between 1 and any value, we will get the two result, either 1 or 0, if the number is odd it will give 1 as an output, if it is even then, it gives 0 as an output. If the number found to be 1, then we are going to increase the count by 1, else it can only 0, so we will decrease the same count value by 1.

While doing this, we should maintain our output, for that if we found the value of count is less than 0, then we will be adding up the value of negativeNum count’s index value to the output and increase the count of negativeNum by 1. Else we only found the number greater than or equal to 0, so we will be adding up the values of the positiveNum count’s index to the output and increase the count of positiveNum by 1. The important thing is whenever we find the same value of both of the hash arrays current index, it means we found an even-odd sub-array for us. And at last, we will return the output.

Implementation

C++ program for Count Subarrays with Same Even and Odd Elements

#include<iostream>
#include<unordered_map>

using namespace std;

int getOESubarrays(int arr[], int n)
{
    int count = 0;
    int output = 0;

    int positiveNum[n+1];
    int negativeNum[n+1];

    positiveNum[0] = 1;

    for (int i = 0; i < n; i++)
    {
        if ((arr[i] & 1) == 1) count++;
        else count--;

        if (count < 0)
        {
            output += negativeNum[-count];
            negativeNum[-count]++;
        }
        else
        {
            output += positiveNum[count];
            positiveNum[count]++;
        }
    }
    return output;
}
int main()
{
    int arr[] = {2,3,4,5,1,6};
    int n = sizeof(arr) / sizeof(arr[0]);
    cout << "Even Odd Sub-Arrays are: " << getOESubarrays(arr,n);
    return 0;
}

Even Odd Sub-Arrays are: 7

Java program for Count Subarrays with Same Even and Odd Elements

class oddEvenSubArrays
{
    public static int getOESubarrays(int[] arr, int n)
    {
        int count = 0;
        int output = 0;

        int positiveNum[] = new int[n + 1];
        int negativeNum[] = new int[n + 1];

        positiveNum[0] = 1;

        for (int i = 0; i < n; i++)
        {
            if ((arr[i] & 1) == 1) count++;
            else count--;

            if (count < 0)
            {
                output += negativeNum[-count];
                negativeNum[-count]++;
            }
            else
            {
                output += positiveNum[count];
                positiveNum[count]++;
            }
        }
        return output;
    }
    public static void main(String[] args)
    {
        int arr[] = {2,3,4,5,1,6};
        int n = arr.length;
        System.out.println("Even Odd Sub-Arrays are: "+getOESubarrays(arr, n));
    }
}

Even Odd Sub-Arrays are: 7