Dada una array binaria arr[] de tamaño N, la tarea es encontrar el recuento de distintos tripletes alternos.
Nota: un triplete se alterna si los valores de esos índices están en forma {0, 1, 0} o {1, 0, 1}.
Ejemplos:
Entrada: arr[] = {0, 0, 1, 1, 0, 1} Salida: 6 Explicación: Aquí existen cuatro secuencias de «010» y dos secuencias de «101». Entonces, el número total de formas de secuencia alterna de tamaño 3 es 6.
Entrada: arr[] = {0, 0, 0, 0, 0}
Salida: 0
Explicación: Como no hay 1 en la array, no podemos encontrar ninguna secuencia alterna de 3 tamaños.
Enfoque ingenuo: El enfoque ingenuo y el enfoque basado en la programación dinámica se mencionan en el Conjunto 1 de este artículo.
Enfoque eficiente : este problema se puede resolver de manera eficiente utilizando la suma de prefijos basada en la siguiente idea:
- Los posibles grupos que se pueden formar son {0, 1, 0} o {1, 0, 1}
- Entonces, para cualquier 1 que se encuentre en la array, las combinaciones posibles totales se pueden calcular encontrando la cantidad de formas de seleccionar un 0 de su izquierda y un 0 de su derecha. Este valor es igual al producto del número de 0 a su izquierda y el número de 0 a su derecha.
- Para un 0, el número de tripletes posibles se puede encontrar de la misma manera.
- La respuesta final es la suma de estos dos valores.
Siga los pasos a continuación para resolver el problema:
- Recorra la array comenzando desde la izquierda y cuente el número de 0 en (digamos count1 ) y el número total de 1 (digamos count2 ).
- Luego, inicialice el conteo izquierdo de ambos números como 0.
- Atraviesa la array de i = 0 a N :
- Ahora, supongamos que se encuentra 1, así que primero calcule las combinaciones posibles de {0, 1, 0} usando este 1. Para esto, multiplique left_count_Zero y count1 y agregue el resultado a nuestra respuesta final.
- Suma este valor con la suma .
- Ahora, disminuya la cuenta 2 como para el siguiente elemento que aparece a la izquierda y, por lo tanto, incremente la cuenta izquierda_Uno .
- Del mismo modo, haga lo mismo cuando se encuentre 0.
- Devolver la suma final .
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ code for the above approach:
#include <bits/stdc++.h>
using namespace std;
// Function to calculate the possible
// number of ways to select 3 numbers
long long numberOfWays(int A[], int N)
{
int left_count_Zero = 0, count1 = 0;
int left_count_One = 0, count2 = 0;
long long ans = 0;
// Storing the right counts of
// 1s and 2s in the array
for (int i = 0; i < N; i++) {
if (A[i] == 1)
count2++;
else
count1++;
}
// Traversing the array from left side
for (int i = 0; i < N; i++) {
// If 1 is encountered,
// looking for all combinations of
// 0, 1, 0 possible
if (A[i] == 1) {
// Number of ways to select one
// 0 from left side * Number of
// ways to select one 0 from right
ans += (left_count_Zero * count1);
// Decrement right_count of 1
// and increment left_count of 1
left_count_One++;
count2--;
}
// If 0 is encountered,
// looking for all combinations
// of 1, 0, 1 possible
else {
// Number of ways to select
// one 1 from left side
// * Number of ways to select a 1
// from right
ans += (left_count_One * count2);
// Decrement right_count of 2
// and increment left_count of 2
left_count_Zero++;
count1--;
}
}
return ans;
}
// Drivers code
int main()
{
int arr[] = { 0, 0, 1, 1, 0, 1 };
int N = 6;
// Function call
cout << numberOfWays(arr, N);
return 0;
}
Java
// Java code for the above approach
import java.io.*;
class GFG
{
// Function to calculate the possible
// number of ways to select 3 numbers
public static long numberOfWays(int A[], int N)
{
int left_count_Zero = 0, count1 = 0;
int left_count_One = 0, count2 = 0;
long ans = 0;
// Storing the right counts of
// 1s and 2s in the array
for (int i = 0; i < N; i++) {
if (A[i] == 1)
count2++;
else
count1++;
}
// Traversing the array from left side
for (int i = 0; i < N; i++) {
// If 1 is encountered,
// looking for all combinations of
// 0, 1, 0 possible
if (A[i] == 1) {
// Number of ways to select one
// 0 from left side * Number of
// ways to select one 0 from right
ans += (left_count_Zero * count1);
// Decrement right_count of 1
// and increment left_count of 1
left_count_One++;
count2--;
}
// If 0 is encountered,
// looking for all combinations
// of 1, 0, 1 possible
else {
// Number of ways to select
// one 1 from left side
// * Number of ways to select a 1
// from right
ans += (left_count_One * count2);
// Decrement right_count of 2
// and increment left_count of 2
left_count_Zero++;
count1--;
}
}
return ans;
}
public static void main(String[] args)
{
int arr[] = { 0, 0, 1, 1, 0, 1 };
int N = 6;
// Function call
System.out.print(numberOfWays(arr, N));
}
}
// This code is contributed by Rohit Pradhan
Python3
# Python code for the above approach: # Function to calculate the possible # number of ways to select 3 numbers def numberOfWays(A, N): left_count_Zero,count1,left_count_One,count2 = 0,0,0,0 ans = 0 # Storing the right counts of # 1s and 2s in the array for i in range(N): if (A[i] == 1): count2 += 1 else: count1 += 1 # Traversing the array from left side for i in range(N): # If 1 is encountered, # looking for all combinations of # 0, 1, 0 possible if (A[i] == 1): # Number of ways to select one # 0 from left side * Number of # ways to select one 0 from right ans += (left_count_Zero * count1) # Decrement right_count of 1 # and increment left_count of 1 left_count_One += 1 count2 -= 1 # If 0 is encountered, # looking for all combinations # of 1, 0, 1 possible else: # Number of ways to select # one 1 from left side # * Number of ways to select a 1 # from right ans += (left_count_One * count2) # Decrement right_count of 2 # and increment left_count of 2 left_count_Zero += 1 count1 -= 1 return ans # Drivers code arr = [0, 0, 1, 1, 0, 1] N = 6 # Function call print(numberOfWays(arr, N)) # This code is contributed by shinjanpatra
C#
// C# code for the above approach
using System;
class GFG {
// Function to calculate the possible
// number of ways to select 3 numbers
static long numberOfWays(int[] A, int N)
{
int left_count_Zero = 0, count1 = 0;
int left_count_One = 0, count2 = 0;
long ans = 0;
// Storing the right counts of
// 1s and 2s in the array
for (int i = 0; i < N; i++) {
if (A[i] == 1)
count2++;
else
count1++;
}
// Traversing the array from left side
for (int i = 0; i < N; i++) {
// If 1 is encountered,
// looking for all combinations of
// 0, 1, 0 possible
if (A[i] == 1) {
// Number of ways to select one
// 0 from left side * Number of
// ways to select one 0 from right
ans += (left_count_Zero * count1);
// Decrement right_count of 1
// and increment left_count of 1
left_count_One++;
count2--;
}
// If 0 is encountered,
// looking for all combinations
// of 1, 0, 1 possible
else {
// Number of ways to select
// one 1 from left side
// * Number of ways to select a 1
// from right
ans += (left_count_One * count2);
// Decrement right_count of 2
// and increment left_count of 2
left_count_Zero++;
count1--;
}
}
return ans;
}
public static int Main()
{
int[] arr = new int[] { 0, 0, 1, 1, 0, 1 };
int N = 6;
// Function call
Console.Write(numberOfWays(arr, N));
return 0;
}
}
// This code is contributed by Taranpreet
Javascript
<script>
// JavaScript code for the above approach:
// Function to calculate the possible
// number of ways to select 3 numbers
const numberOfWays = (A, N) => {
let left_count_Zero = 0, count1 = 0;
let left_count_One = 0, count2 = 0;
let ans = 0;
// Storing the right counts of
// 1s and 2s in the array
for (let i = 0; i < N; i++) {
if (A[i] == 1)
count2++;
else
count1++;
}
// Traversing the array from left side
for (let i = 0; i < N; i++) {
// If 1 is encountered,
// looking for all combinations of
// 0, 1, 0 possible
if (A[i] == 1) {
// Number of ways to select one
// 0 from left side * Number of
// ways to select one 0 from right
ans += (left_count_Zero * count1);
// Decrement right_count of 1
// and increment left_count of 1
left_count_One++;
count2--;
}
// If 0 is encountered,
// looking for all combinations
// of 1, 0, 1 possible
else {
// Number of ways to select
// one 1 from left side
// * Number of ways to select a 1
// from right
ans += (left_count_One * count2);
// Decrement right_count of 2
// and increment left_count of 2
left_count_Zero++;
count1--;
}
}
return ans;
}
// Drivers code
let arr = [0, 0, 1, 1, 0, 1];
let N = 6;
// Function call
document.write(numberOfWays(arr, N));
// This code is contributed by rakeshsahni
</script>
Producción
6
Complejidad temporal: O(N)
Espacio auxiliar: O(1)