Contar subarreglos con los mismos elementos pares e impares

Dada una array de N enteros, cuente el número de subarreglos pares e impares. Un subarreglo par-impar es un subarreglo que contiene el mismo número de enteros pares e impares. 
Ejemplos: 
 

Input : arr[] = {2, 5, 7, 8} 
Output : 3
Explanation : There are total 3 even-odd subarrays.
               1) {2, 5}
               2) {7, 8}
               3) {2, 5, 7, 8}

Input : arr[] = {3, 4, 6, 8, 1, 10} 
Output : 3
Explanation : In this case, 3 even-odd subarrays are:
               1) {3, 4}
               2) {8, 1}
               3) {1, 10}

Este problema es principalmente una variación de los subarreglos de conteo con el mismo número de 0 y 1 s.
Un enfoque ingenuo sería verificar todos los subarreglos posibles utilizando dos bucles, ya sean subarreglos pares-impares o no. Este enfoque llevará  tiempo.
Un enfoque eficiente resuelve el problema en tiempo O(N) y se basa en las siguientes ideas: 
 

• Los subarreglos pares e impares siempre tendrán la misma longitud.
• Seguimiento de la diferencia entre la frecuencia de números enteros pares e impares.
• El hashing de esta diferencia de frecuencias es útil para encontrar el número de subarreglos pares e impares.

La idea básica es utilizar la diferencia entre la frecuencia de los números pares e impares para obtener una solución óptima. Mantendremos dos arrays hash de enteros para el valor positivo y negativo de la diferencia. 
-> Ejemplo para entender mejor: 
-> Considere diferencia = freq(impar) – freq(par) 
-> Para calcular esta diferencia, incremente el valor de ‘diferencia’ cuando hay 
un entero impar y disminuya cuando hay un incluso entero. (inicialmente, diferencia = 0) 
arr[] = {3, 4, 6, 8, 1, 10}
índice 0 1 2 3 4 5 6
array 3 4 6 8 1 10
diferencia 0 1 0 -1 -2 -1 – 2
-> Observe que cada vez que un valor ‘k’ se repite en la array ‘diferencia’, existe una 
subarreglo par-impar para cada aparición anterior de ese valor, es decir, existe un subarreglo desde 
el índice i + 1 hasta j donde diferencia[i] = k y diferencia[j] = k. 
-> El valor ‘0’ se repite en la array de ‘diferencia’ en el índice 2 y, por lo tanto, existe un subarreglo para los 
índices (0, 2). De manera similar, para la repetición de los valores ‘-1’ (en los índices 3 y 5) y ‘-2’ (en  los
índices 4 y 6), existe un subarreglo para los índices (3, 5] y (4, 6].
A continuación se muestra la implementación de la solución  O(N) descrita anteriormente.
 

/*C++ program to find total number of
even-odd subarrays present in given array*/
#include <bits/stdc++.h>
using namespace std;
 
// function that returns the count of subarrays that
// contain equal number of odd as well as even numbers
int countSubarrays(int arr[], int n)
{
    // initialize difference and answer with 0
    int difference = 0;
    int ans = 0;
 
    // create two auxiliary hash arrays to count frequency
    // of difference, one array for non-negative difference
    // and other array for negative difference. Size of these
    // two auxiliary arrays is 'n+1' because difference can
    // reach maximum value 'n' as well as minimum value '-n'
    int hash_positive[n + 1], hash_negative[n + 1];
 
    // initialize these auxiliary arrays with 0
    fill_n(hash_positive, n + 1, 0);
    fill_n(hash_negative, n + 1, 0);
 
    // since the difference is initially 0, we have to
    // initialize hash_positive[0] with 1
    hash_positive[0] = 1;
 
    // for loop to iterate through whole
    // array (zero-based indexing is used)
    for (int i = 0; i < n ; i++)
    {
        // incrementing or decrementing difference based on
        // arr[i] being even or odd, check if arr[i] is odd
        if (arr[i] & 1 == 1)
            difference++;
        else
            difference--;
 
        // adding hash value of 'difference' to our answer
        // as all the previous occurrences of the same
        // difference value will make even-odd subarray
        // ending at index 'i'. After that, we will increment
        // hash array for that 'difference' value for
        // its occurrence at index 'i'. if difference is
        // negative then use hash_negative
        if (difference < 0)
        {
            ans += hash_negative[-difference];
            hash_negative[-difference]++;
        }
         
        // else use hash_positive
        else
        {
            ans += hash_positive[difference];
            hash_positive[difference]++;
        }
    }
 
    // return total number of even-odd subarrays
    return ans;
}
 
// Driver code
int main()
{
    int arr[] = {3, 4, 6, 8, 1, 10, 5, 7};
    int n = sizeof(arr) / sizeof(arr[0]);
     
    // Printing total number of even-odd subarrays
    cout << "Total Number of Even-Odd subarrays"
        " are " << countSubarrays(arr,n);
 
    return 0;
}
 
// This code is contributed by Aditya Kumar (adityakumar129)

/*C program to find total number of
even-odd subarrays present in given array*/
#include <stdio.h>
 
// function that returns the count of subarrays that
// contain equal number of odd as well as even numbers
int countSubarrays(int arr[], int n)
{
    // initialize difference and answer with 0
    int difference = 0;
    int ans = 0;
 
    // create two auxiliary hash arrays to count frequency
    // of difference, one array for non-negative difference
    // and other array for negative difference. Size of
    // these two auxiliary arrays is 'n+1' because
    // difference can reach maximum value 'n' as well as
    // minimum value '-n'
    int hash_positive[n + 1], hash_negative[n + 1];
 
    // initialize these auxiliary arrays with 0
    for (int i = 0; i < n + 1; i++)
        hash_positive[i] = 0;
    for (int i = 0; i < n + 1; i++)
        hash_negative[i] = 0;
 
    // since the difference is initially 0, we have to
    // initialize hash_positive[0] with 1
    hash_positive[0] = 1;
 
    // for loop to iterate through whole
    // array (zero-based indexing is used)
    for (int i = 0; i < n; i++) {
        // incrementing or decrementing difference based on
        // arr[i] being even or odd, check if arr[i] is odd
        if (arr[i] & 1 == 1)
            difference++;
        else
            difference--;
 
        // adding hash value of 'difference' to our answer
        // as all the previous occurrences of the same
        // difference value will make even-odd subarray
        // ending at index 'i'. After that, we will
        // increment hash array for that 'difference' value
        // for its occurrence at index 'i'. if difference is
        // negative then use hash_negative
        if (difference < 0) {
            ans += hash_negative[-difference];
            hash_negative[-difference]++;
        }
 
        // else use hash_positive
        else {
            ans += hash_positive[difference];
            hash_positive[difference]++;
        }
    }
 
    // return total number of even-odd subarrays
    return ans;
}
 
// Driver code
int main()
{
    int arr[] = { 3, 4, 6, 8, 1, 10, 5, 7 };
    int n = sizeof(arr) / sizeof(arr[0]);
 
    // Printing total number of even-odd subarrays
    printf("Total Number of Even-Odd subarrays are %d ",
           countSubarrays(arr, n));
 
    return 0;
}
 
// This code is contributed by Aditya Kumar (adityakumar129)

// Java program to find total number of even-odd subarrays
// present in given array
class GFG {
 
    // function that returns the count of subarrays that
    // contain equal number of odd as well as even numbers
    static int countSubarrays(int[] arr, int n)
    {
        // initialize difference and answer with 0
        int difference = 0;
        int ans = 0;
 
        // create two auxiliary hash arrays to count
        // frequency of difference, one array for
        // non-negative difference and other array for
        // negative difference. Size of these two auxiliary
        // arrays is 'n+1' because difference can reach
        // maximum value 'n' as well as minimum value '-n'
        // initialize these auxiliary arrays with 0
        int[] hash_positive = new int[n + 1];
        int[] hash_negative = new int[n + 1];
 
        // since the difference is initially 0, we have to
        // initialize hash_positive[0] with 1
        hash_positive[0] = 1;
 
        // for loop to iterate through whole array
        // (zero-based indexing is used)
        for (int i = 0; i < n; i++) {
            // incrementing or decrementing difference based
            // on arr[i] being even or odd, check if arr[i]
            // is odd
            if ((arr[i] & 1) == 1)
                difference++;
            else
                difference--;
 
            // adding hash value of 'difference' to our
            // answer as all the previous occurrences of the
            // same difference value will make even-odd
            // subarray ending at index 'i'. After that, we
            // will increment hash array for that
            // 'difference' value for its occurrence at
            // index 'i'. if difference is negative then use
            // hash_negative
            if (difference < 0) {
                ans += hash_negative[-difference];
                hash_negative[-difference]++;
            } // else use hash_positive
            else {
                ans += hash_positive[difference];
                hash_positive[difference]++;
            }
        }
 
        // return total number of even-odd subarrays
        return ans;
    }
 
    // Driver code
    public static void main(String[] args)
    {
        int[] arr = new int[] { 3, 4, 6, 8, 1, 10, 5, 7 };
        int n = arr.length;
 
        // Printing total number of even-odd subarrays
        System.out.println(
            "Total Number of Even-Odd subarrays are "
            + countSubarrays(arr, n));
    }
}
 
// This code is contributed by Aditya Kumar (adityakumar129)

# Python3 program to find total
# number of even-odd subarrays
# present in given array
 
# function that returns the count
# of subarrays that contain equal
# number of odd as well as even numbers
def countSubarrays(arr, n):
 
    # initialize difference and
    # answer with 0
    difference = 0
    ans = 0
 
    # create two auxiliary hash
    # arrays to count frequency
    # of difference, one array
    # for non-negative difference
    # and other array for negative
    # difference. Size of these two
    # auxiliary arrays is 'n+1'
    # because difference can reach
    # maximum value 'n' as well as
    # minimum value '-n'
    hash_positive = [0] * (n + 1)
    hash_negative = [0] * (n + 1)
 
    # since the difference is
    # initially 0, we have to
    # initialize hash_positive[0] with 1
    hash_positive[0] = 1
 
    # for loop to iterate through
    # whole array (zero-based
    # indexing is used)
    for i in range(n):
     
        # incrementing or decrementing
        # difference based on arr[i]
        # being even or odd, check if
        # arr[i] is odd
        if (arr[i] & 1 == 1):
            difference = difference + 1
        else:
            difference = difference - 1
 
        # adding hash value of 'difference'
        # to our answer as all the previous
        # occurrences of the same difference
        # value will make even-odd subarray
        # ending at index 'i'. After that,
        # we will increment hash array for
        # that 'difference' value for
        # its occurrence at index 'i'. if
        # difference is negative then use
        # hash_negative
        if (difference < 0):
            ans += hash_negative[-difference]
            hash_negative[-difference] = hash_negative[-difference] + 1
         
        # else use hash_positive
        else:
            ans += hash_positive[difference]
            hash_positive[difference] = hash_positive[difference] + 1
 
    # return total number of
    # even-odd subarrays
    return ans
 
# Driver code
arr = [3, 4, 6, 8, 1, 10, 5, 7]
n = len(arr)
 
# Printing total number
# of even-odd subarrays
print("Total Number of Even-Odd subarrays are " +
                    str(countSubarrays(arr, n)))
 
# This code is contributed
# by Yatin Gupta

// C# program to find total
// number of even-odd subarrays
// present in given array
using System;
 
class GFG
{
    // function that returns the
    // count of subarrays that
    // contain equal number of
    // odd as well as even numbers
    static int countSubarrays(int []arr,
                              int n)
    {
        // initialize difference
        // and answer with 0
        int difference = 0;
        int ans = 0;
     
        // create two auxiliary hash
        // arrays to count frequency
        // of difference, one array
        // for non-negative difference
        // and other array for negative
        // difference. Size of these
        // two auxiliary arrays is 'n+1'
        // because difference can
        // reach maximum value 'n' as
        // well as minimum value '-n'
        int []hash_positive = new int[n + 1];
        int []hash_negative = new int[n + 1];
     
        // initialize these
        // auxiliary arrays with 0
        Array.Clear(hash_positive, 0, n + 1);
        Array.Clear(hash_negative, 0, n + 1);
     
        // since the difference is
        // initially 0, we have to
        // initialize hash_positive[0] with 1
        hash_positive[0] = 1;
     
        // for loop to iterate
        // through whole array
        // (zero-based indexing is used)
        for (int i = 0; i < n ; i++)
        {
            // incrementing or decrementing
            // difference based on
            // arr[i] being even or odd,
            // check if arr[i] is odd
            if ((arr[i] & 1) == 1)
                difference++;
            else
                difference--;
     
            // adding hash value of 'difference'
            // to our answer as all the previous
            // occurrences of the same difference
            // value will make even-odd subarray
            // ending at index 'i'. After that,
            // we will increment hash array for
            // that 'difference' value for its
            // occurrence at index 'i'. if
            // difference is negative then use
            // hash_negative
            if (difference < 0)
            {
                ans += hash_negative[-difference];
                hash_negative[-difference]++;
            }
             
            // else use hash_positive
            else
            {
                ans += hash_positive[difference];
                hash_positive[difference]++;
            }
        }
     
        // return total number
        // of even-odd subarrays
        return ans;
    }
     
    // Driver code
    static void Main()
    {
        int []arr = new int[]{3, 4, 6, 8,
                              1, 10, 5, 7};
        int n = arr.Length;
         
        // Printing total number
        // of even-odd subarrays
        Console.Write("Total Number of Even-Odd" +
                               " subarrays are " +
                           countSubarrays(arr,n));
    }
}
 
// This code is contributed by
// Manish Shaw(manishshaw1)

<?php
// PHP program to find total number of
// even-odd subarrays present in given array
 
// function that returns the count of subarrays
// that contain equal number of odd as well
// as even numbers
function countSubarrays(&$arr, $n)
{
    // initialize difference and
    // answer with 0
    $difference = 0;
    $ans = 0;
 
    // create two auxiliary hash arrays to count
    // frequency of difference, one array for
    // non-negative difference and other array
    // for negative difference. Size of these
    // two auxiliary arrays is 'n+1' because
    // difference can reach maximum value 'n'
    // as well as minimum value '-n'
    $hash_positive = array_fill(0, $n + 1, NULL);
    $hash_negative = array_fill(0, $n + 1, NULL);
 
    // since the difference is initially 0, we
    // have to initialize hash_positive[0] with 1
    $hash_positive[0] = 1;
 
    // for loop to iterate through whole
    // array (zero-based indexing is used)
    for ($i = 0; $i < $n ; $i++)
    {
        // incrementing or decrementing difference
        // based on arr[i] being even or odd, check
        // if arr[i] is odd
        if ($arr[$i] & 1 == 1)
            $difference++;
        else
            $difference--;
 
        // adding hash value of 'difference' to our
        // answer as all the previous occurrences of
        // the same difference value will make even-odd
        // subarray ending at index 'i'. After that, we
        // will increment hash array for that 'difference'
        // value for its occurrence at index 'i'. if
        // difference is negative then use hash_negative
        if ($difference < 0)
        {
            $ans += $hash_negative[-$difference];
            $hash_negative[-$difference]++;
        }
         
        // else use hash_positive
        else
        {
            $ans += $hash_positive[$difference];
            $hash_positive[$difference]++;
        }
    }
 
    // return total number of even-odd
    // subarrays
    return $ans;
}
 
// Driver code
$arr = array(3, 4, 6, 8, 1, 10, 5, 7);
$n = sizeof($arr);
 
// Printing total number of even-odd
// subarrays
echo "Total Number of Even-Odd subarrays".
     " are " . countSubarrays($arr, $n);
 
// This code is contributed by ita_c
?>

<script>
// Javascript program to find total
// number of even-odd subarrays
// present in given array
     
    // function that returns the
    // count of subarrays that
    // contain equal number of
    // odd as well as even numbers
    function countSubarrays(arr, n)
    {
     
        // initialize difference
        // and answer with 0
        let difference = 0;
        let ans = 0;
   
        // create two auxiliary hash
        // arrays to count frequency
        // of difference, one array
        // for non-negative difference
        // and other array for negative
        // difference. Size of these
        // two auxiliary arrays is 'n+1'
        // because difference can
        // reach maximum value 'n' as
        // well as minimum value '-n'
        // initialize these
        // auxiliary arrays with 0
        let hash_positive = new Array(n + 1);
        let hash_negative = new Array(n + 1);
        for(let i=0;i<n+1;i++)
        {
            hash_positive[i] = 0;
            hash_negative[i] = 0;
             
        }
   
        // since the difference is
        // initially 0, we have to
        // initialize hash_positive[0] with 1
        hash_positive[0] = 1;
   
        // for loop to iterate
        // through whole array
        // (zero-based indexing is used)
        for (let i = 0; i < n; i++)
        {
         
            // incrementing or decrementing
            // difference based on
            // arr[i] being even or odd,
            // check if arr[i] is odd
            if ((arr[i] & 1) == 1)
            {
                difference++;
            }
            else
            {
                difference--;
            }
   
            // adding hash value of 'difference'
            // to our answer as all the previous
            // occurrences of the same difference
            // value will make even-odd subarray
            // ending at index 'i'. After that,
            // we will increment hash array for
            // that 'difference' value for its
            // occurrence at index 'i'. if
            // difference is negative then use
            // hash_negative
            if (difference < 0)
            {
                ans += hash_negative[-difference];
                hash_negative[-difference]++;
            }
             
            // else use hash_positive
            else
            {
                ans += hash_positive[difference];
                hash_positive[difference]++;
            }
        }
   
        // return total number
        // of even-odd subarrays
        return ans;
    }
     
    // Driver code
    let arr = [3, 4, 6, 8,
            1, 10, 5, 7];
    let n = arr.length;
     
    // Printing total number
        // of even-odd subarrays
    document.write("Total Number of Even-Odd"
                + " subarrays are "
                + countSubarrays(arr, n));
             
    // This code is contributed by avanitrachhadiya2155
</script>

Total Number of Even-Odd subarrays are 7

Complejidad temporal: O(N), donde N es el número de enteros. 
Espacio Auxiliar : O(2N), donde N es el número de enteros.