Contar subarreglos con el mismo conteo de ocurrencias de tres números dados

Dado un arreglo arr[] y tres enteros X, Y, Z , la tarea es encontrar el número de subarreglos del arreglo en el que el número de ocurrencias de X, Y y Z es igual.

Ejemplos:

Entrada: arr[] = {3, 6, 7, 8, 3, 6, 7}, X = 3, Y = 6, Z = 7
Salida: 8
Explicación: Hay 8 de esos subarreglos, es decir, {3, 6, 7 }, {6, 7, 8, 3}, {7, 8, 3, 6}, {8}, {3, 6, 7, 8}, {8, 3, 6, 7}, {3, 6 , 7}, {3, 6, 7, 8, 3, 6, 7}, en los que el recuento de ocurrencias de 3, 6 y 7 es igual.

Entrada: arr[] = {23, 45, 76, 45, 76, 87, 23}, X = 23, Y = 45, Z = 76
Salida: 4
Explicación: Hay 3 de esos subarreglos, es decir, {23, 45, 76 }, {45, 76, 87, 23}, {87}, {23, 45, 76, 45, 76, 87, 23}, en el que el recuento de ocurrencias de 23, 45 y 76 es igual.

Enfoque: siga los pasos a continuación para resolver el problema:

1. Inicialice tres variables, digamos fNum_count = 0, sNum_count = 0 y tNum_count = 0 y mini .
2. Inicializa un Map , int>, int> .
3. Incrementa la frecuencia de {0, 0, 0} una vez.
4. Recorra la array y, si se encuentra alguno de los números dados, incremente su cuenta correspondiente y disminuya el mínimo de los tres de todos ellos.
5. Después del recorrido, incremente la frecuencia del conjunto de valores de estas tres variables.
6. Ahora inicialice una variable, digamos final_ans.
7. Recorra el mapa y agregue v*(v-1) / 2 de cada frecuencia a final_ans .
8. Imprima final_ans como la respuesta requerida.

A continuación se muestra la implementación del enfoque anterior:

// C++ program for the above approach
 
#include <bits/stdc++.h>
using namespace std;
 
typedef long long ll;
 
// Function to count subarrays
void countSubarrays(int arr[], int N,
                    int X, int Y, int Z)
{
 
    map<pair<pair<int, int>, int>, int> m;
    m[{ { 0, 0 }, 0 }]++;
 
    int fNum_count = 0, sNum_count = 0,
        tNum_count = 0;
    int mini;
 
    // Traverse the array
    for (int i = 0; i < N; ++i) {
 
        // Check is arr[i] is equal to X
        if (arr[i] == X) {
 
            // Increment fNum_count
            fNum_count++;
 
            mini = min(min(fNum_count,
                           sNum_count),
                       tNum_count);
            fNum_count -= mini;
            sNum_count -= mini;
            tNum_count -= mini;
        }
 
        // Check is arr[i] is equal to Y
        else if (arr[i] == Y) {
 
            // Increment the count of sNum_count
            sNum_count++;
 
            mini = min(min(fNum_count,
                           sNum_count),
                       tNum_count);
            fNum_count -= mini;
            sNum_count -= mini;
            tNum_count -= mini;
        }
 
        // Check is arr[i] is equal to Z
        else if (arr[i] == Z) {
 
            // Increment the count of
            // tNum_count
            tNum_count++;
 
            mini = min(min(fNum_count,
                           sNum_count),
                       tNum_count);
            fNum_count -= mini;
            sNum_count -= mini;
            tNum_count -= mini;
        }
        m[{ { fNum_count, sNum_count },
            tNum_count }]++;
    }
 
    ll final_ans = 0;
    map<pair<pair<int, int>, int>,
        int>::iterator it;
 
    // Iterate over the map
    for (it = m.begin(); it != m.end();
         ++it) {
        ll val = it->second;
        final_ans += (val * (val - 1)) / 2;
    }
 
    // Print the  answer
    cout << final_ans;
}
 
// Driver Code
int main()
{
    // Given array
    int arr[] = { 3, 6, 7, 8, 3, 6, 7 };
 
    // Size of the array
    int N = sizeof(arr) / sizeof(arr[0]);
 
    // Given value of X, Y & Z
    int X = 3, Y = 6, Z = 7;
 
    // Function Call
    countSubarrays(arr, N, X, Y, Z);
 
    return 0;
}

# Python3 program for the above approach
 
# Function to count subarrays
def countSubarrays(arr, N, X, Y, Z):
    m = {}
    m[(  ( 0, 0 ), 0 )] = 1
    fNum_count, sNum_count = 0, 0
    tNum_count = 0
    mini = 0
 
    # Traverse the array
    for i in range(N):
 
        # Check is arr[i] is equal to X
        if (arr[i] == X):
 
            # Increment fNum_count
            fNum_count += 1
 
            mini = min(min(fNum_count,sNum_count),tNum_count)
            fNum_count -= mini
            sNum_count -= mini
            tNum_count -= mini
 
        # Check is arr[i] is equal to Y
        elif (arr[i] == Y):
 
            # Increment the count of sNum_count
            sNum_count+=1
 
            mini = min(min(fNum_count,sNum_count), tNum_count)
 
            fNum_count -= mini
            sNum_count -= mini
            tNum_count -= mini
 
        # Check is arr[i] is equal to Z
        elif (arr[i] == Z):
 
            # Increment the count of
            # tNum_count
            tNum_count +=1
 
            mini = min(min(fNum_count, sNum_count), tNum_count)
 
            fNum_count -= mini
            sNum_count -= mini
            tNum_count -= mini
 
        m[(( fNum_count, sNum_count ),tNum_count )] = m.get((( fNum_count, sNum_count ),tNum_count ),0)+1
 
    final_ans = 0
     
    # Iterate over the map
    for it in m:
        val = m[it]
        final_ans += (val * (val - 1)) // 2
 
    # Print the  answer
    print (final_ans)
 
# Driver Code
if __name__ == '__main__':
   
    # Given array
    arr = [3, 6, 7, 8, 3, 6, 7]
 
    # Size of the array
    N = len(arr)
 
    # Given value of X, Y & Z
    X, Y, Z = 3, 6, 7
 
    # Function Call
    countSubarrays(arr, N, X, Y, Z)
 
    # This code is contributed by mohit kumar 29.

8

Complejidad temporal: O(N * LogN)
Espacio auxiliar: O(N)