Recuento de todas las posibles strings binarias equilibradas de longitud N

Posted on by Rudeus Greyrat

Dado un número N , la tarea es encontrar el número total de strings binarias balanceadas posibles de longitud N. Se dice que una string binaria está balanceada si:

  • El número de 0 y 1 es igual en cada string binaria
  • El conteo de 0s en cualquier prefijo de strings binarias siempre es mayor o igual al conteo de 1s
  • Por ejemplo: 01 es una string binaria balanceada de longitud 2, pero 10 no lo es.

Ejemplo:

Entrada: N = 4
Salida: 2
Explicación: Las strings binarias balanceadas posibles son: 0101, 0011

Entrada: N = 5
Salida: 0

Enfoque: El problema dado se puede resolver de la siguiente manera:

  1. Si N es impar, entonces no es posible una string binaria balanceada ya que la condición de un conteo igual de 0s y 1s fallará.
  2. Si N es par, entonces la string binaria de longitud N tendrá N/2 pares equilibrados de 0 y 1.
  3. Entonces, ahora intente crear una fórmula para obtener el número de strings balanceadas cuando N es par.

Entonces, si N = 2 , entonces la posible string binaria balanceada será solo «01» , ya que «00» y «11» no tienen el mismo conteo de 0s y 1s y «10» no tiene un conteo de 0s >= conteo de 1s en el prefijo [0, 1).
De manera similar, si N=4 , la posible string binaria balanceada será “0101” y “0011”.
Para N = 6 , la posible string binaria balanceada será “010101” , “010011” , “001101” , “000111” y “001011”
Ahora, si consideramos esta serie:
Para N=0, cuenta(0) = 1
Para N=2, cuenta(2) = cuenta(0)*cuenta(0) = 1
Para N=4, cuenta(4) = cuenta(0)*cuenta(2) + cuenta(2)*cuenta(0) = 1*1 + 1*1 = 2
Para N=6, cuenta(6) = cuenta (0)*cuenta(4) + cuenta(2)*cuenta(2) + cuenta(4)*cuenta(0) = 1*2 + 1*1 + 2*1 = 5
Para N=8, cuenta(8 ) = cuenta(0)*cuenta(6) + cuenta(2)*cuenta(4) + cuenta(4)*cuenta(2) + cuenta(6)*cuenta(0) = 1*5 + 1*2 + 2*1 + 5*1 = 14
.
.
.
Para N=N, cuenta(N) = cuenta(0)*cuenta(N-2) + cuenta(2)*cuenta(N-4) + cuenta(4)*cuenta(N-6) + …. + cuenta (N-6) * cuenta (4) + cuenta (N-4) * cuenta (2) + cuenta (N-2) * cuenta (0)
que no es más que números catalanes .

  1. Por lo tanto, para cualquier N par, devuelva el número catalán para (N/2) como respuesta.

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;
 
#define MAXN 500
#define mod 1000000007
 
// Vector to store catalan number
vector<long long int> cat(MAXN + 1, 0);
 
// Function to get the Catalan Number
void catalan()
{
    cat[0] = 1;
    cat[1] = 1;
 
    for (int i = 2; i < MAXN + 1; i++) {
        long long int t = 0;
        for (int j = 0; j < i; j++) {
            t += ((cat[j] % mod)
                  * (cat[i - 1 - j] % mod)
                  % mod);
        }
        cat[i] = (t % mod);
    }
}
 
int countBalancedStrings(int N)
{
    // If N is odd
    if (N & 1) {
        return 0;
    }
 
    // Returning Catalan number
    // of N/2 as the answer
    return cat[N / 2];
}
 
// Driver Code
int main()
{
    // Precomputing
    catalan();
 
    int N = 4;
    cout << countBalancedStrings(N);
}

Java

// Java program for the above approach
class GFG {
 
    public static int MAXN = 500;
    public static int mod = 1000000007;
 
    // Vector to store catalan number
    public static int[] cat = new int[MAXN + 1];
 
    // Function to get the Catalan Number
    public static void catalan() {
        cat[0] = 1;
        cat[1] = 1;
 
        for (int i = 2; i < MAXN + 1; i++) {
            int t = 0;
            for (int j = 0; j < i; j++) {
                t += ((cat[j] % mod)
                        * (cat[i - 1 - j] % mod)
                        % mod);
            }
            cat[i] = (t % mod);
        }
    }
 
    public static int countBalancedStrings(int N)
    {
       
        // If N is odd
        if ((N & 1) > 0) {
            return 0;
        }
 
        // Returning Catalan number
        // of N/2 as the answer
        return cat[N / 2];
    }
 
    // Driver Code
    public static void main(String args[])
    {
       
        // Precomputing
        catalan();
 
        int N = 4;
        System.out.println(countBalancedStrings(N));
    }
}
 
// This code is contributed by saurabh_jaiswal.

Python3

# Python3 program for the above approach
MAXN = 500
mod = 1000000007
 
# Vector to store catalan number
cat = [0 for _ in range(MAXN + 1)]
 
# Function to get the Catalan Number
def catalan():
     
    global cat
 
    cat[0] = 1
    cat[1] = 1
 
    for i in range(2, MAXN + 1):
        t = 0
        for j in range(0, i):
            t += ((cat[j] % mod) *
                  (cat[i - 1 - j] % mod) % mod)
 
        cat[i] = (t % mod)
 
def countBalancedStrings(N):
 
    # If N is odd
    if (N & 1):
        return 0
 
    # Returning Catalan number
    # of N/2 as the answer
    return cat[N // 2]
 
# Driver Code
if __name__ == "__main__":
 
    # Precomputing
    catalan()
 
    N = 4
    print(countBalancedStrings(N))
 
# This code is contributed by rakeshsahni

C#

// C# program for the above approach
using System;
class GFG
{
    public static int MAXN = 500;
    public static int mod = 1000000007;
 
    // Vector to store catalan number
    public static int[] cat = new int[MAXN + 1];
 
    // Function to get the Catalan Number
    public static void catalan()
    {
        cat[0] = 1;
        cat[1] = 1;
 
        for (int i = 2; i < MAXN + 1; i++)
        {
            int t = 0;
            for (int j = 0; j < i; j++)
            {
                t += ((cat[j] % mod)
                        * (cat[i - 1 - j] % mod)
                        % mod);
            }
            cat[i] = (t % mod);
        }
    }
 
    public static int countBalancedStrings(int N)
    {
 
        // If N is odd
        if ((N & 1) > 0)
        {
            return 0;
        }
 
        // Returning Catalan number
        // of N/2 as the answer
        return cat[N / 2];
    }
 
    // Driver Code
    public static void Main()
    {
 
        // Precomputing
        catalan();
 
        int N = 4;
        Console.Write(countBalancedStrings(N));
    }
}
 
// This code is contributed by saurabh_jaiswal.

Javascript

<script>
 
    // JavaScript Program to implement
    // the above approach
    let MAXN = 500
    let mod = 1000000007
 
    // Vector to store catalan number
    let cat = new Array(MAXN + 1).fill(0);
 
    // Function to get the Catalan Number
    function catalan() {
        cat[0] = 1;
        cat[1] = 1;
 
        for (let i = 2; i < MAXN + 1; i++) {
            let t = 0;
            for (let j = 0; j < i; j++) {
                t += ((cat[j] % mod)
                    * (cat[i - 1 - j] % mod)
                    % mod);
            }
            cat[i] = (t % mod);
        }
    }
 
    function countBalancedStrings(N)
    {
     
        // If N is odd
        if (N & 1) {
            return 0;
        }
 
        // Returning Catalan number
        // of N/2 as the answer
        return cat[Math.floor(N / 2)];
    }
 
    // Driver Code
 
    // Precomputing
    catalan();
    let N = 4;
    document.write(countBalancedStrings(N));
 
// This code is contributed by Potta Lokesh
</script>
Producción

2

Tiempo Complejidad: O(N 2 )
Espacio Auxiliar: O(N)

Publicación traducida automáticamente

Artículo escrito por Code_r y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *