Dada una array binaria arr[] , la tarea es contar el número de subarreglos que tienen el mismo conteo de 0 s y 1 s, y todos los 0 s y 1 s se colocan consecutivamente en ese subarreglo.
Ejemplos:
Entrada: arr[] = {1, 0, 1, 1}
Salida: 2
Explicación: Los subarreglos que satisfacen las condiciones dadas son {1, 0} y {0, 1}. Por lo tanto, la cuenta de dichos subarreglos es 2.Entrada: arr[] = {1, 1, 0, 0, 1, 0}
Salida: 4
Explicación: Los subarreglos que satisfacen las condiciones dadas son {1, 1, 0, 0}, {1, 0}, {0, 1}, {1, 0}. Por lo tanto, la cuenta de dichos subarreglos es 4.
Enfoque ingenuo: el enfoque más simple es atravesar la array dada y, para cada par de elementos adyacentes desiguales, iterar a la izquierda y a la derecha del índice actual y verificar si el conteo de 1 s y 0 s es igual o no. Incremente el recuento de subarreglos hasta que se descubra que es falso. Después de completar el recorrido de la array, imprima el recuento total de subarreglos.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
// Function to count subarrays
// having equal count of 0s and 1s
// with all 0s and all 1s grouped together
void countSubarrays(int A[], int N)
{
// Stores the count of subarrays
int ans = 0;
for (int i = 0; i < N - 1; i++) {
// If current element is different
// from the next array element
if (A[i] != A[i + 1]) {
// Increment count
ans++;
// Count the frequency of
// 1s and 0s
for (int j = i - 1, k = i + 2;
j >= 0 && k < N
&& A[j] == A[i]
&& A[k] == A[i + 1];
j--, k++) {
// Increment count
ans++;
}
}
}
// Print the final count
cout << ans << "\n";
}
// Driver Code
int main()
{
int A[] = { 1, 1, 0, 0, 1, 0 };
int N = sizeof(A) / sizeof(A[0]);
// Function Call
countSubarrays(A, N);
return 0;
}
Java
// Java program for the above approach
import java.util.*;
class GFG
{
// Function to count subarrays
// having equal count of 0s and 1s
// with all 0s and all 1s grouped together
static void countSubarrays(int A[], int N)
{
// Stores the count of subarrays
int ans = 0;
for (int i = 0; i < N - 1; i++)
{
// If current element is different
// from the next array element
if (A[i] != A[i + 1])
{
// Increment count
ans++;
// Count the frequency of
// 1s and 0s
for (int j = i - 1, k = i + 2;
j >= 0 && k < N
&& A[j] == A[i]
&& A[k] == A[i + 1];
j--, k++)
{
// Increment count
ans++;
}
}
}
// Print the final count
System.out.print(ans+ "\n");
}
// Driver Code
public static void main(String[] args)
{
int A[] = { 1, 1, 0, 0, 1, 0 };
int N = A.length;
// Function Call
countSubarrays(A, N);
}
}
// This code is contributed by shikhasingrajput
Python3
# Python3 program for the above approach # Function to count subarrays # having equal count of 0s and 1s # with all 0s and all 1s grouped together def countSubarrays(A, N) : # Stores the count of subarrays ans = 0; for i in range(N - 1) : # If current element is different # from the next array element if (A[i] != A[i + 1]) : # Increment count ans += 1; # Count the frequency of # 1s and 0s j = i - 1; k = i + 2; while (j >= 0 and k < N and A[j] == A[i] and A[k] == A[i + 1]) : # Increment count ans += 1; j -= 1; k += 1; # Print the final count print(ans); # Driver Code if __name__ == "__main__" : A = [ 1, 1, 0, 0, 1, 0 ]; N = len(A); # Function Call countSubarrays(A, N); # This code is contributed by AnkitRai01
C#
// C# program for the above approach
using System;
class GFG{
// Function to count subarrays
// having equal count of 0s and 1s
// with all 0s and all 1s grouped together
static void countSubarrays(int[] A, int N)
{
// Stores the count of subarrays
int ans = 0;
for(int i = 0; i < N - 1; i++)
{
// If current element is different
// from the next array element
if (A[i] != A[i + 1])
{
// Increment count
ans++;
// Count the frequency of
// 1s and 0s
for(int j = i - 1, k = i + 2;
j >= 0 && k < N &&
A[j] == A[i] &&
A[k] == A[i + 1];
j--, k++)
{
// Increment count
ans++;
}
}
}
// Print the final count
Console.Write(ans + "\n");
}
// Driver Code
public static void Main()
{
int[] A = { 1, 1, 0, 0, 1, 0 };
int N = A.Length;
// Function Call
countSubarrays(A, N);
}
}
// This code is contributed by sanjoy_62
Javascript
<script>
// JavaScript program to implement
// the above approach
// Function to count subarrays
// having equal count of 0s and 1s
// with all 0s and all 1s grouped together
function countSubarrays(A, N)
{
// Stores the count of subarrays
let ans = 0;
for (let i = 0; i < N - 1; i++)
{
// If current element is different
// from the next array element
if (A[i] != A[i + 1])
{
// Increment count
ans++;
// Count the frequency of
// 1s and 0s
for (let j = i - 1, k = i + 2;
j >= 0 && k < N
&& A[j] == A[i]
&& A[k] == A[i + 1];
j--, k++)
{
// Increment count
ans++;
}
}
}
// Print the final count
document.write(ans+ "<br/>");
}
// Driver Code
let A = [ 1, 1, 0, 0, 1, 0 ];
let N = A.length;
// Function Call
countSubarrays(A, N);
</script>
Producción:
4
Complejidad de Tiempo: O(N 2 )
Espacio Auxiliar: O(1)
Enfoque eficiente: para optimizar el enfoque anterior, siga los pasos a continuación:
- Inicialice una variable, digamos res , para almacenar el recuento de subarreglos.
- Inicialice una variable, digamos curr , con el primer valor de la array y una array cnt[] , para realizar un seguimiento de los elementos consecutivos.
- Atraviese la array y realice los siguientes pasos:
- Si el elemento actual es igual a curr , incrementa el último valor de cnt[] .
- De lo contrario, actualice curr al elemento actual y agregue 1 a la array cnt[] .
- Recorra la array cnt[] y encuentre la suma del mínimo de los elementos adyacentes y agréguela a la variable res . Esto asegura que la frecuencia de los elementos sea igual.
- Después de completar los pasos anteriores, imprima el valor de res como el recuento resultante de subarreglos.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
// Function to count subarrays
// having equal count of 0s and 1s
// with all 0s and all 1s grouped together
void countSubarrays(int A[], int N)
{
// Stores the count
int res = 0;
// Initialize cur with first element
int curr = A[0];
vector<int> cnt = {1};
for (int c = 1; c < N; c++)
{
// If the next element is same
// as the current element
if (A == curr)
// Increment count
cnt[cnt.size() - 1]++;
else
// Update curr
curr = A;
cnt.push_back(1);
}
// Iterate over the array count
for (int i = 1; i < cnt.size(); i++)
{
// Consider the minimum
res += min(cnt[i - 1], cnt[i]);
}
cout << (res - 1);
}
// Driver code
int main()
{
// Given arr[]
int A[] = { 1, 1, 0, 0, 1, 0 };
int N = sizeof(A) / sizeof(A[0]);
// Function Call
countSubarrays(A, N);
return 0;
}
// This code is contributed by divyesh072019
Java
import java.util.Vector;
// Java program for the above approach
class GFG {
// Function to count subarrays
// having equal count of 0s and 1s
// with all 0s and all 1s grouped together
static void countSubarrays(int[] A)
{
// Stores the count
int res = 0;
// Initialize cur with first element
int curr = A[0];
int[] cnt = new int[A.length];
cnt[0] = 1;
for (int c = 1; c < A.length; c++) {
// If the next element is same
// as the current element
if (A == curr)
// Increment count
cnt++;
else
// Update curr
curr = A;
cnt = 1;
}
// Iterate over the array count
for (int i = 1; i < cnt.length; i++) {
// Consider the minimum
res += Math.min(cnt[i - 1], cnt[i]);
}
System.out.println(res - 1);
}
// Driver code
public static void main(String[] args)
{
// Given arr[]
int[] A = { 1, 1, 0, 0, 1, 0 };
// Function Call
countSubarrays(A);
}
}
// This code is contributed by 29AjayKumar
Python3
# Python3 program for the above approach # Function to count subarrays # having equal count of 0s and 1s # with all 0s and all 1s grouped together def countSubarrays(A): # Stores the count res = 0 # Initialize cur with first element curr, cnt = A[0], [1] for c in A[1:]: # If the next element is same # as the current element if c == curr: # Increment count cnt[-1] += 1 else: # Update curr curr = c cnt.append(1) # Iterate over the array count for i in range(1, len(cnt)): # Consider the minimum res += min(cnt[i - 1], cnt[i]) print(res - 1) # Given arr[] A = [1, 1, 0, 0, 1, 0] # Function Call countSubarrays(A)
C#
// C# program for the above approach
using System;
class GFG{
// Function to count subarrays
// having equal count of 0s and 1s
// with all 0s and all 1s grouped together
static void countSubarrays(int[] A)
{
// Stores the count
int res = 0;
// Initialize cur with first element
int curr = A[0];
int[] cnt = new int[A.Length];
cnt[0] = 1;
for(int c = 1; c < A.Length; c++)
{
// If the next element is same
// as the current element
if (A == curr)
// Increment count
cnt++;
else
// Update curr
curr = A;
cnt = 1;
}
// Iterate over the array count
for(int i = 1; i < cnt.Length; i++)
{
// Consider the minimum
res += Math.Min(cnt[i - 1], cnt[i]);
}
Console.WriteLine(res - 1);
}
// Driver code
public static void Main(String[] args)
{
// Given []arr
int[] A = { 1, 1, 0, 0, 1, 0 };
// Function Call
countSubarrays(A);
}
}
// This code is contributed by Amit Katiyar
Javascript
<script>
// Javascript program for the above approach
// Function to count subarrays
// having equal count of 0s and 1s
// with all 0s and all 1s grouped together
function countSubarrays( A, N)
{
// Stores the count
var res = 0;
// Initialize cur with first element
var curr = A[0];
var cnt = [];
cnt.fill(1)
for (var c = 1; c < N; c++)
{
// If the next element is same
// as the current element
if (A == curr)
// Increment count
cnt[cnt.length - 1]++;
else
// Update curr
curr = A;
cnt.push(1);
}
// Iterate over the array count
for (var i = 1; i < cnt.length; i++)
{
// Consider the minimum
res += Math.min(cnt[i - 1], cnt[i]);
}
document.write (res);
}
var A = [ 1, 1, 0, 0, 1, 0 ];
var N = A.length;
// Function Call
countSubarrays(A, N);
// This code is contributed by SoumikMondal
</script>
Producción:
4
Complejidad temporal: O(N)
Espacio auxiliar: O(N)
Publicación traducida automáticamente
Artículo escrito por koulick_sadhu y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA