Contar subarreglos con el mismo número de ocurrencias de dos elementos dados

Dada una array y dos números enteros, digamos, x e y, encuentre el número de subarreglos en los que el número de ocurrencias de x es igual al número de ocurrencias de y.

Ejemplos: 

Input : arr[] = {1, 2, 1},
        x = 1, y = 2 
Output : 2
The possible sub-arrays have same equal number 
of occurrences of x and y are:
1) {1, 2}, x and y have same occurrence(1).
2) {2, 1}, x and y have same occurrence(1).

Input : arr[] = {1, 2, 1},
        x = 4, y = 6
Output : 6
The possible sub-arrays have same equal number of 
occurrences of x and y are:
1) {1}, x and y have same occurrence(0).
2) {2}, x and y have same occurrence(0).
3) {1}, x and y have same occurrence(0).
1) {1, 2}, x and y have same occurrence(0).
2) {2, 1}, x and y have same occurrence(0).
3) {1, 2, 1}, x and y have same occurrence(0).

Input : arr[] = {1, 2, 1},
        x = 1, y = 1
Output : 6
The possible sub-arrays have same equal number 
of occurrences of x and y are:
1) {1}, x and y have same occurrence(1).
2) {2}, x and y have same occurrence(0).
3) {1}, x and y have same occurrence(1).
1) {1, 2}, x and y have same occurrence(1).
2) {2, 1}, x and y have same occurrence(1).
3) {1, 2, 1}, x and y have same occurrences (2).

Simplemente podemos generar todos los subconjuntos posibles y comprobar para cada subarreglo si el número de ocurrencias de x es igual al de y en ese subarreglo en particular. 

Implementación:

/* C++ program to count number of sub-arrays in which
   number of occurrence of x is equal to that of y
    using brute force */
#include <bits/stdc++.h>
using namespace std;
 
int sameOccurrence(int arr[], int n, int x, int y)
{
    int result = 0;
 
    // Check for each subarray for the required condition
    for (int i = 0; i <= n - 1; i++) {
        int ctX = 0,  ctY = 0;
        for (int j = i; j <= n - 1; j++) {
            if (arr[j] == x)
                ctX += 1;
            else if (arr[j] == y)
                ctY += 1;
            if (ctX == ctY)
                result += 1;           
        }
    }
 
    return (result);
}
 
// Driver code
int main()
{
    int arr[] = { 1, 2, 2, 3, 4, 1 };
    int n = sizeof(arr) / sizeof(arr[0]);
    int x = 2, y = 3;
    cout << sameOccurrence(arr, n, x, y);
    return (0);
}

/* Java program to count number of sub-arrays in which
number of occurrence of x is equal to that of y
    using brute force */
import java.util.*;
 
class solution
{
 
static int sameOccurrence(int arr[], int n, int x, int y)
{
    int result = 0;
 
    // Check for each subarray for the required condition
    for (int i = 0; i <= n - 1; i++) {
        int ctX = 0, ctY = 0;
        for (int j = i; j <= n - 1; j++) {
            if (arr[j] == x)
                ctX += 1;
            else if (arr[j] == y)
                ctY += 1;
            if (ctX == ctY)
                result += 1;        
        }
    }
 
    return (result);
}
 
// Driver code
public static void main(String args[])
{
    int arr[] = { 1, 2, 2, 3, 4, 1 };
    int n = arr.length;
    int x = 2, y = 3;
    System.out.println(sameOccurrence(arr, n, x, y));
 
}
}
 
// This code is contributed by
// Sahil_shelangia

# Python 3 program to count number of
# sub-arrays in which number of occurrence
# of x is equal to that of y using brute force
def sameOccurrence(arr, n, x, y):
    result = 0
 
    # Check for each subarray for
    # the required condition
    for i in range(n):
        ctX = 0
        ctY = 0
        for j in range(i, n, 1):
            if (arr[j] == x):
                ctX += 1;
            elif (arr[j] == y):
                ctY += 1
            if (ctX == ctY):
                result += 1
 
    return (result)
 
# Driver code
if __name__ == '__main__':
    arr = [1, 2, 2, 3, 4, 1]
    n = len(arr)
    x = 2
    y = 3
    print(sameOccurrence(arr, n, x, y))
 
# This code is contributed by
# Surendra_Gangwar

/* C# program to count number of sub-arrays in which
number of occurrence of x is equal to that of y
using brute force */
using System;
 
class GFG
{
 
static int sameOccurrence(int[] arr, int n,
                            int x, int y)
{
    int result = 0;
 
    // Check for each subarray for
    // the required condition
    for (int i = 0; i <= n - 1; i++)
    {
        int ctX = 0, ctY = 0;
        for (int j = i; j <= n - 1; j++)
        {
            if (arr[j] == x)
                ctX += 1;
            else if (arr[j] == y)
                ctY += 1;
            if (ctX == ctY)
                result += 1;        
        }
    }
    return (result);
}
 
// Driver code
public static void Main()
{
    int[] arr = { 1, 2, 2, 3, 4, 1 };
    int n = arr.Length;
    int x = 2, y = 3;
    Console.Write(sameOccurrence(arr, n, x, y));
 
}
}
 
// This code is contributed by Ita_c.

<?php
// PHP program to count number of sub-arrays
// in which number of occurrence of x is equal
// to that of y using brute force
 
function sameOccurrence($arr, $n, $x, $y)
{
    $result = 0;
 
    // Check for each subarray for the
    // required condition
    for ($i = 0; $i <= $n - 1; $i++)
    {
        $ctX = 0; $ctY = 0;
        for ( $j = $i; $j <= $n - 1; $j++)
        {
            if ($arr[$j] == $x)
                $ctX += 1;
            else if ($arr[$j] == $y)
                $ctY += 1;
            if ($ctX == $ctY)
                $result += 1;    
        }
    }
 
    return ($result);
}
 
// Driver code
$arr = array( 1, 2, 2, 3, 4, 1 );
$n = count($arr);
$x = 2; $y = 3;
echo sameOccurrence($arr, $n, $x, $y);
 
// This code is contributed by 29AjayKumar
?>

<script>
 
// Javascript program to count number
// of sub-arrays in which number of
// occurrence of x is equal to that of y
// using brute force
function sameOccurrence(arr, n, x, y)
{
    let result = 0;
     
    // Check for each subarray for the
    // required condition
    for(let i = 0; i <= n - 1; i++)
    {
        let ctX = 0, ctY = 0;
        for(let j = i; j <= n - 1; j++)
        {
            if (arr[j] == x)
                ctX += 1;
            else if (arr[j] == y)
                ctY += 1;
            if (ctX == ctY)
                result += 1;        
        }
    }
    return(result);
}
 
// Driver code
let arr = [ 1, 2, 2, 3, 4, 1 ];
let n = arr.length;
let x = 2, y = 3;
 
document.write(sameOccurrence(arr, n, x, y));
 
// This code is contributed by avanitrachhadiya2155
 
</script>

7

Complejidad de tiempo – O(N^2) 
Espacio auxiliar – O(1)

Enfoque Eficiente (O(N) Tiempo Complejidad) :

En esta solución, el espacio auxiliar es O(N) y la complejidad temporal también es O(N). Creamos dos arrays, por ejemplo, countX[] y countY[], que denotan el número de ocurrencias de x e y, respectivamente, hasta ese punto en la array. Luego, evaluamos otra array, digamos diff que almacena (countX[i]-countY[i]), yo soy el índice de la array. Ahora, almacene el conteo de cada elemento de la array diff en un mapa, digamos m. Inicialice el resultado como m[0] ya que la aparición de 0 en la array diff nos da un recuento de subarreglo donde se cumple la condición requerida. 

Ahora, itere a través del mapa y use la fórmula del apretón de manos, actualice el resultado, ya que dos valores iguales en el arreglo diff indican que el subarreglo contiene el mismo número de ocurrencias de x e y.

Explanation:
arr[] = {1, 2, 2, 3, 4, 1};
x = 2, y = 3;

Two arrays countX[] and countY[] are be evaluated as-
countX[] = {0, 1, 2, 2, 2, 2};
countY[] = {0, 0, 0, 1, 1, 1};

Hence, diff[] = {0, 1, 2, 1, 1, 1}; 
(diff[i] = countX[i]-countY[i], i be the index of array)

Now, create a map and store the count of each element of diff in it,
so, finally, we get-
m[0] = 1, m[1] = 4, m[2] = 1;

Initialize result as m[0]
i.e result = m[0] = 1

Further, using handshake formula, updating the 
result as follows-
result  = result + (1*(1-1))/2 = 1 + 0 = 1
result  = result + (4*(4-1))/2 = 1 + 6 = 7
result  = result + (1*(1-1))/2 = 7 + 0 = 7

so, the final result will be 7, required subarrays having 
same number of occurrences of x and y.

Implementación:

/* C++ program to count number of sub-arrays in which
  number of occurrence of x is equal to that of y using
  efficient approach in terms of time */
#include <bits/stdc++.h>
using namespace std;
 
int sameOccurrence(int arr[], int n, int x, int y)
{
    int countX[n], countY[n];
 
    map<int, int> m; // To store counts of same diffs
 
    // Count occurrences of x and y
    for (int i = 0; i < n; i++) {
        if (arr[i] == x) {
            if (i != 0)
                countX[i] = countX[i - 1] + 1;
            else
                countX[i] = 1;
        } else {
            if (i != 0)
                countX[i] = countX[i - 1];
            else
                countX[i] = 0;
        }
        if (arr[i] == y) {
            if (i != 0)
                countY[i] = countY[i - 1] + 1;
            else
                countY[i] = 1;
        } else {
            if (i != 0)
                countY[i] = countY[i - 1];
            else
                countY[i] = 0;
        }
   
         // Increment count of current
         m[countX[i] - countY[i]]++;
    }
 
    // Traverse map and commute result.
    int result = m[0];
    for (auto it = m.begin(); it != m.end(); it++)
        result = result + ((it->second) * ((it->second) - 1)) / 2;
     
    return (result);
}
 
// Driver code
int main()
{
    int arr[] = { 1, 2, 2, 3, 4, 1 };
    int n = sizeof(arr) / sizeof(arr[0]);
    int x = 2, y = 3;
    cout << sameOccurrence(arr, n, x, y);
    return (0);
}

/* Java program to count number of sub-arrays in which
number of occurrence of x is equal to that of y using
efficient approach in terms of time */
import java.util.*;
 
class GFG
{
 
static int sameOccurrence(int arr[], int n, int x, int y)
{
    int []countX = new int[n];
    int []countY = new int[n];
 
    Map<Integer,Integer> m = new HashMap<>();
     
    // To store counts of same diff
    // Count occurrences of x and y
    for (int i = 0; i < n; i++)
    {
        if (arr[i] == x)
        {
            if (i != 0)
                countX[i] = countX[i - 1] + 1;
            else
                countX[i] = 1;
        }
        else
        {
            if (i != 0)
                countX[i] = countX[i - 1];
            else
                countX[i] = 0;
        }
        if (arr[i] == y)
        {
            if (i != 0)
                countY[i] = countY[i - 1] + 1;
            else
                countY[i] = 1;
        }
        else
        {
            if (i != 0)
                countY[i] = countY[i - 1];
            else
                countY[i] = 0;
        }
     
        // Increment count of current
        if(m.containsKey(countX[i] - countY[i]))
        {
            m.put(countX[i] - countY[i], m.get(countX[i] - countY[i])+1);
        }
        else
        {
            m.put(countX[i] - countY[i], 1);
        }
    }
 
    // Traverse map and commute result.
    int result = m.get(0);
    for (Map.Entry<Integer,Integer> it : m.entrySet())
        result = result + ((it.getValue()) * ((it.getValue()) - 1)) / 2;
     
    return (result);
}
 
// Driver code
public static void main(String[] args)
{
    int arr[] = { 1, 2, 2, 3, 4, 1 };
    int n = arr.length;
    int x = 2, y = 3;
    System.out.println(sameOccurrence(arr, n, x, y));
}
}
 
// This code is contributed by Rajput-Ji

# Python3 program to count number of
# sub-arrays in which number of occurrence
# of x is equal to that of y using efficient
# approach in terms of time */
def sameOccurrence( arr, n, x, y):
 
    countX = [0 for i in range(n)]
    countY = [0 for i in range(n)]
 
    # To store counts of same diffs
    m = dict()
 
    # Count occurrences of x and y
    for i in range(n):
        if (arr[i] == x):
            if (i != 0):
                countX[i] = countX[i - 1] + 1
            else:
                countX[i] = 1
        else:
            if (i != 0):
                countX[i] = countX[i - 1]
            else:
                countX[i] = 0
 
        if (arr[i] == y):
            if (i != 0):
                countY[i] = countY[i - 1] + 1
            else:
                countY[i] = 1
        else:
            if (i != 0):
                countY[i] = countY[i - 1]
            else:
                countY[i] = 0
         
        # Increment count of current
        m[countX[i] - countY[i]] = m.get(countX[i] -
                                         countY[i], 0) + 1
     
    # Traverse map and commute result.
    result = m[0]
    for j in m:
        result += (m[j] * (m[j] - 1)) // 2
     
    return result
 
# Driver code
arr = [1, 2, 2, 3, 4, 1]
n = len(arr)
x, y = 2, 3
print(sameOccurrence(arr, n, x, y))
  
# This code is contributed
# by mohit kumar

/* C# program to count number of sub-arrays in which
number of occurrence of x is equal to that of y using
efficient approach in terms of time */
using System;
using System.Collections.Generic;
 
class GFG
{
 
static int sameOccurrence(int []arr, int n, int x, int y)
{
    int []countX = new int[n];
    int []countY = new int[n];
 
    Dictionary<int,int> m = new Dictionary<int,int>();
     
    // To store counts of same diff
    // Count occurrences of x and y
    for (int i = 0; i < n; i++)
    {
        if (arr[i] == x)
        {
            if (i != 0)
                countX[i] = countX[i - 1] + 1;
            else
                countX[i] = 1;
        }
        else
        {
            if (i != 0)
                countX[i] = countX[i - 1];
            else
                countX[i] = 0;
        }
        if (arr[i] == y)
        {
            if (i != 0)
                countY[i] = countY[i - 1] + 1;
            else
                countY[i] = 1;
        }
        else
        {
            if (i != 0)
                countY[i] = countY[i - 1];
            else
                countY[i] = 0;
        }
     
        // Increment count of current
        if(m.ContainsKey(countX[i] - countY[i]))
        {
            var v = m[countX[i] - countY[i]]+1;
            m.Remove(countX[i] - countY[i]);
            m.Add(countX[i] - countY[i], v);
        }
        else
        {
            m.Add(countX[i] - countY[i], 1);
        }
    }
 
    // Traverse map and commute result.
    int result = m[0];
    foreach(KeyValuePair<int, int> it in m)
        result = result + ((it.Value) * ((it.Value) - 1)) / 2;
     
    return (result);
}
 
// Driver code
public static void Main(String[] args)
{
    int []arr = { 1, 2, 2, 3, 4, 1 };
    int n = arr.Length;
    int x = 2, y = 3;
    Console.WriteLine(sameOccurrence(arr, n, x, y));
}
}
 
// This code is contributed by Princi Singh

<script>
 
/* Javascript program to count number of sub-arrays in which
number of occurrence of x is equal to that of y using
efficient approach in terms of time */
     
    function sameOccurrence(arr,n,x,y)
    {
        let countX = new Array(n);
        let countY = new Array(n);
         
        let m = new Map();
         
        // To store counts of same diff
    // Count occurrences of x and y
    for (let i = 0; i < n; i++)
    {
        if (arr[i] == x)
        {
            if (i != 0)
                countX[i] = countX[i - 1] + 1;
            else
                countX[i] = 1;
        }
        else
        {
            if (i != 0)
                countX[i] = countX[i - 1];
            else
                countX[i] = 0;
        }
        if (arr[i] == y)
        {
            if (i != 0)
                countY[i] = countY[i - 1] + 1;
            else
                countY[i] = 1;
        }
        else
        {
            if (i != 0)
                countY[i] = countY[i - 1];
            else
                countY[i] = 0;
        }
      
        // Increment count of current
        if(m.has(countX[i] - countY[i]))
        {
            m.set(countX[i] - countY[i], m.get(countX[i] - countY[i])+1);
        }
        else
        {
            m.set(countX[i] - countY[i], 1);
        }
    }
  
    // Traverse map and commute result.
    let result = m.get(0);
    for (let [key, value] of m.entries())
        result = result + (value) * ((value) - 1) / 2;
      
    return (result);
    }
     
    // Driver code
    let arr=[1, 2, 2, 3, 4, 1];
    let n = arr.length;
    let x = 2, y = 3;
    document.write(sameOccurrence(arr, n, x, y));
     
     
    // This code is contributed by rag2127
</script>

7

Tiempo Complejidad – O(N) 
Espacio Auxiliar – O(N)

Este artículo es una contribución de Divyanshu_Gupta . Si te gusta GeeksforGeeks y te gustaría contribuir, también puedes escribir un artículo usando write.geeksforgeeks.org o enviar tu artículo por correo a review-team@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks.