Odd-Even Subarrays

You are given an array A of N positive integer values. A subarray of this array is called Odd-Even subarray if the number of odd integers in this subarray is equal to the number of even integers in this subarray.

Find the number of Odd-Even subarrays for the given array.

Example:

Input:  n = 4, arr = [1,2,1,2]
Output: 4

Approach

C++

#include <bits/stdc++.h>
using namespace std;

long long oddEvenSubarray(long long a[], long long n)
{
    long long hash_pos[n + 1], hash_neg[n + 1], 
diff = 0, ans = 0;
    fill_n(hash_pos, n + 1, 0);
    fill_n(hash_neg, n + 1, 0);
    hash_pos[0] = 1;
    for (long long i = 0; i < n; i++)
    {
        if (a[i] & 1 == 1)
            diff++;
        else
            diff--;
        if (diff < 0)
        {
            ans += hash_neg[-diff];
            hash_neg[-diff]++;
        }
        else
        {
            ans += hash_pos[diff];
            hash_pos[diff]++;
        }
    }
    return ans;
}
int main()
{
    long long n = 4;

    long long arr[n] = {1, 2, 1, 2};

    cout << oddEvenSubarray(arr, n) << "\n";

    return 0;
}


No comments:

Post a Comment