Recuento de distintos tripletes alternos de índices de una array dada

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: la idea básica para resolver este problema es la siguiente:

Encuentre todos los tripletes y verifique cuáles de ellos siguen la propiedad alterna.

Siga los pasos mencionados a continuación para implementar la idea:

• Use tres bucles anidados para señalar i, j, k tales que ( i < j < k ).
• Compruebe si arr[i] < arr[j] > arr[k] o arr[i] > arr[j] < arr[k] .
  • Si es así, incrementa la respuesta.
  • De lo contrario, continúa con la iteración.
• Devuelve el recuento final de trillizos.

Complejidad del tiempo:O(N ³ )
Espacio Auxiliar:O(1)

Enfoque eficiente: este problema se puede resolver de manera eficiente utilizando programación dinámica basada en la siguiente idea:

El recuento de subsecuencias alternas que terminan en el j-ésimo índice que tiene tamaño i es igual a la suma de los valores de todas las subsecuencias que tienen tamaño i-1 y tienen un valor diferente de arr[j].
Por lo tanto, el concepto de programación dinámica se puede utilizar aquí. 

Para utilizar el concepto de programación dinámica, forme una array dp[][] donde dp[i][j] almacena el recuento de la subsecuencia alterna con tamaño i y que termina en el índice jth . Aquí no puedo exceder de 3 porque necesitamos encontrar trillizos.

Siga los pasos mencionados a continuación para implementar la idea: 

• Declare una array 2D (digamos dp[][] ) que tenga (4 filas) y (N + 1 columnas) e inicialícela con el valor 0 .
• Iterar de i = 1 a 3 para posibles longitudes de subsecuencia:
  • Ahora iterar de j = 0 a N-1 (considerando que j es el último índice de tal subsecuencia):
    • Si el tamaño de la secuencia es 1 o digamos (i == 1) , entonces dp[i][j] = 1 porque solo hay una forma de crear una secuencia de 1 tamaño con un elemento.
    • De lo contrario, itere desde k = 0 hasta j para encontrar cualquier elemento anterior que sea diferente de arr[j] .
    • Si existe, agregue dp[i][k] a dp[i][j].
• Devuelve el número de tripletes posibles que es igual a la suma de los valores almacenados en la fila dp[3][j] .

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

// C++ code to implement the approach
 
#include <bits/stdc++.h>
using namespace std;
 
// Function to find the distinct ways to
// find alternate sequence of size 3.
long long numberOfWays(vector<int>& s,
                       int n)
{
 
    int size = 3;
    long long ans = 0;
 
    // Declaring a 2d dp
    vector<vector<long long> > dp(size + 1,
                                  vector<long long>(
                                      n + 1, 0));
 
    for (int i = 1; i <= size; i++) {
        for (int j = 0; j < n; j++) {
 
            // Filling the first row with 1.
            if (i == 1) {
                dp[i][j] = 1;
            }
            else {
 
                // Finding the sum of
                // all sequences
                // which are ending with
                // alternate number
                for (int k = 0; k < j; k++) {
                    if (s[k] != s[j]) {
                        dp[i][j] += dp[i - 1][k];
                    }
                }
            }
        }
    }
 
    // Answer is the sum of last row of dp
    for (int i = 0; i < n; i++) {
        ans += dp[size][i];
    }
    return ans;
}
 
// Driver code
int main()
{
    vector<int> arr = { 0, 0, 1, 1, 0, 1 };
    int N = arr.size();
    cout << numberOfWays(arr, N);
    return 0;
}

// Java code to implement the approach
import java.io.*;
 
class GFG
{
 
  // Function to find the distinct ways to
  // find alternate sequence of size 3.
  public static long numberOfWays(int s[], int n)
  {
 
    int size = 3;
    long ans = 0;
 
    // Declaring a 2d dp
    long dp[][] = new long[size + 1][n + 1];
 
    for (int i = 1; i <= size; i++) {
      for (int j = 0; j < n; j++) {
 
        // Filling the first row with 1.
        if (i == 1) {
          dp[i][j] = 1;
        }
        else {
 
          // Finding the sum of
          // all sequences
          // which are ending with
          // alternate number
          for (int k = 0; k < j; k++) {
            if (s[k] != s[j]) {
              dp[i][j] += dp[i - 1][k];
            }
          }
        }
      }
    }
 
    // Answer is the sum of last row of dp
    for (int i = 0; i < n; i++) {
      ans += dp[size][i];
    }
    return ans;
  }
 
  public static void main(String[] args)
  {
    int arr[] = { 0, 0, 1, 1, 0, 1 };
    int N = arr.length;
    System.out.print(numberOfWays(arr, N));
  }
}
 
// This code is contributed by Rohit Pradhan

# Python program for above approach
   
# Function to find the distinct ways to
# find alternate sequence of size 3.
def numberOfWays(s, n) :
 
    size = 3
    ans = 0
 
    # Declaring a 2d dp
    dp = [[0]* (n + 1)]* (size + 1)
 
    for i in range(1, size-1, 1) :
        for j in range(0, n, 1) :
 
            # Filling the first row with 1.
            if (i == 1) :
                dp[i][j] = 1
             
            else :
 
                # Finding the sum of
                # all sequences
                # which are ending with
                # alternate number
                for k in range(0, j, 1) :
                    if (s[k] != s[j]) :
                        dp[i][j] += dp[i - 1][k]
                         
     
 
    # Answer is the sum of last row of dp
    for i in range(0, n) :
         
        ans += dp[size][i]
     
    return ans
 
# Driver code
 
if __name__ == "__main__":
     
    arr = [ 0, 0, 1, 1, 0, 1 ]
    N = len(arr)
    print(numberOfWays(arr, N))
 
# This code is contributed by code_hunt.

// C# code to implement the approach
using System;
 
public class GFG{
 
  // Function to find the distinct ways to
  // find alternate sequence of size 3.
  public static long numberOfWays(int[] s, int n)
  {
 
    int size = 3;
    long ans = 0;
 
    // Declaring a 2d dp
    long[,] dp = new long[size + 1,n + 1];
 
    for (int i = 1; i <= size; i++) {
      for (int j = 0; j < n; j++) {
 
        // Filling the first row with 1.
        if (i == 1) {
          dp[i, j] = 1;
        }
        else {
 
          // Finding the sum of
          // all sequences
          // which are ending with
          // alternate number
          for (int k = 0; k < j; k++) {
            if (s[k] != s[j]) {
              dp[i, j] += dp[i - 1, k];
            }
          }
        }
      }
    }
 
    // Answer is the sum of last row of dp
    for (int i = 0; i < n; i++) {
      ans += dp[size, i];
    }
    return ans;
  }
 
  static public void Main (){
 
    int[] arr = { 0, 0, 1, 1, 0, 1 };
    int N = arr.Length;
    Console.Write(numberOfWays(arr, N));
  }
}
 
// This code is contributed by hrithikgarg03188.

<script>
// JS code to implement the approach
 
// Function to find the distinct ways to
// find alternate sequence of size 3.
function numberOfWays(s, n)
{
 
    var size = 3;
    var ans = 0;
 
    // Declaring a 2d dp
    var dp = [];
    for (var i = 0; i <= size; i++) {
        dp.push([]);
        for (var j = 0; j <= n; j++)
            dp[i].push(0);
    }
 
    for (var i = 1; i <= size; i++) {
        for (var j = 0; j < n; j++) {
 
            // Filling the first row with 1.
            if (i == 1) {
                dp[i][j] = 1;
            }
            else {
 
                // Finding the sum of
                // all sequences
                // which are ending with
                // alternate number
                for (var k = 0; k < j; k++) {
                    if (s[k] != s[j]) {
                        dp[i][j] += dp[i - 1][k];
                    }
                }
            }
        }
    }
 
    // Answer is the sum of last row of dp
    for (var i = 0; i < n; i++) {
        ans += dp[size][i];
    }
 
    return ans;
}
 
// Driver code
 
var arr = [ 0, 0, 1, 1, 0, 1 ];
var N = arr.length;
document.write(numberOfWays(arr, N));
 
// This code is contributed by phasing17
</script>

6

Complejidad del tiempo:O(N ² )
Espacio Auxiliar:EN)