Conteo de strings binarias de longitud N que tienen igual conteo de 0 y 1 y conteo de 1 ≥ conteo de 0 en cada substring de prefijo

Dado un entero N , la tarea es encontrar el número de strings binarias posibles de longitud N con una frecuencia igual de 0 y 1 en las que la frecuencia de 1 sea mayor o igual a la frecuencia de 0 en cada substring de prefijo.

Ejemplos:

Entrada: N = 2
Salida: 1
Explicación:
Todas las strings binarias posibles de longitud 2 son {“00”, “01”, “10” y “11”}. 
De estas 4 strings, solo » 01 » y » 10 » tienen la misma cantidad de 0 y 1.
De estas dos strings, solo » 10 » contiene más o el mismo número de 1 que de 0 en cada substring de prefijo.

Entrada: N = 4
Salida: 2
Explicación: 
Todas las strings binarias posibles de longitud 4, que cumplen las condiciones requeridas, son «1100» y «1010».

Enfoque ingenuo: 
el enfoque más simple es generar todas las strings binarias de longitud N e iterar cada string para verificar si contiene un recuento igual de 0 y 1 y también verificar si la frecuencia de 1 es igual a mayor que la de 0 ‘s en todas sus substrings de prefijo .

Complejidad de tiempo: O(N*2 ^{^N} )
Espacio auxiliar: O(1)

Enfoque eficiente: 
el enfoque anterior se puede optimizar aún más utilizando el concepto de número catalán . Solo necesitamos verificar la paridad de N.

• Si N es un número entero impar , las frecuencias de 0 y 1 no pueden ser iguales. Por lo tanto, el conteo de dichas strings requeridas es 0 .
• Si N es un número entero par , el recuento de substrings requeridas es igual al (N/2) ^número catalán .

Ilustración:  
N = 2 
La única string posible es “ 10 ”. Por lo tanto, la cuenta es 1. 
N = 4 
Las únicas strings posibles son «1100» y «1010». Por lo tanto, la cuenta es 2. 
N = 6 
Las únicas strings posibles son «111000», «110100», «110010», «101010» y «101100». 
Por lo tanto la cuenta es 5. 
Por lo tanto, para cada valor par de N, sigue la secuencia 1 2 5 14 …… 
Por lo tanto, la serie es la de los números catalanes. 
Por tanto, se puede concluir que si N es un entero par, la cuenta es igual a la del (N/2) ^Número Catalán. 
 

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

// C++ Program to implement
// the above approach
#include <bits/stdc++.h>
using namespace std;
 
// Function to calculate and returns the
// value of Binomial Coefficient C(n, k)
unsigned long int binomialCoeff(unsigned int n,
                                unsigned int k)
{
    unsigned long int res = 1;
 
    // Since C(n, k) = C(n, n-k)
    if (k > n - k)
        k = n - k;
 
    // Calculate the value of
    // [n*(n-1)*---*(n-k+1)] / [k*(k-1)*---*1]
    for (int i = 0; i < k; ++i) {
        res *= (n - i);
        res /= (i + 1);
    }
 
    return res;
}
 
// Function to return the count of all
// binary strings having equal count of 0's
// and 1's and each prefix substring having
// frequency of 1's >= frequencies of 0's
unsigned long int countStrings(unsigned int N)
{
    // If N is odd
    if (N % 2 == 1)
 
        // No such strings possible
        return 0;
 
    // Otherwise
    else {
        N /= 2;
 
        // Calculate value of 2nCn
        unsigned long int c
            = binomialCoeff(2 * N, N);
 
        // Return 2nCn/(n+1)
        return c / (N + 1);
    }
}
 
// Driver Code
int main()
{
    int N = 6;
    cout << countStrings(N) << " ";
    return 0;
}

// Java program to implement the
// above approach
import java.util.*;
 
class GFG{
 
// Function to calculate and returns the
// value of Binomial Coefficient C(n, k)
static long binomialCoeff(int n, int k)
{
    long res = 1;
 
    // Since C(n, k) = C(n, n-k)
    if (k > n - k)
        k = n - k;
 
    // Calculate the value of
    // [n*(n-1)*---*(n-k+1)] / [k*(k-1)*---*1]
    for(int i = 0; i < k; ++i)
    {
        res *= (n - i);
        res /= (i + 1);
    }
    return res;
}
 
// Function to return the count of all
// binary strings having equal count of 0's
// and 1's and each prefix substring having
// frequency of 1's >= frequencies of 0's
static long countStrings(int N)
{
     
    // If N is odd
    if (N % 2 == 1)
 
        // No such strings possible
        return 0;
 
    // Otherwise
    else
    {
        N /= 2;
 
        // Calculate value of 2nCn
        long c = binomialCoeff(2 * N, N);
 
        // Return 2nCn/(n+1)
        return c / (N + 1);
    }
}
 
// Driver code
public static void main(String[] args)
{
    int N = 6;
     
    System.out.print(countStrings(N) + " ");
}
}
 
// This code is contributed by offbeat

# Python3 Program to implement
# the above approach
 
# Function to calculate and returns the
# value of Binomial Coefficient C(n, k)
def binomialCoeff(n, k):
    res = 1
 
    # Since C(n, k) = C(n, n-k)
    if (k > n - k):
        k = n - k
 
    # Calculate the value of
    # [n*(n-1)*---*(n-k+1)] / [k*(k-1)*---*1]
    for i in range(k):
        res *= (n - i)
        res //= (i + 1)
 
    return res
 
# Function to return the count of all
# binary strings having equal count of 0's
# and 1's and each prefix substring having
# frequency of 1's >= frequencies of 0's
def countStrings(N):
     
    # If N is odd
    if (N % 2 == 1):
 
        # No such strings possible
        return 0
 
    # Otherwise
    else:
        N //= 2
 
        # Calculate value of 2nCn
        c= binomialCoeff(2 * N, N)
 
        # Return 2nCn/(n+1)
        return c // (N + 1)
 
# Driver Code
if __name__ == '__main__':
    N = 6
    print(countStrings(N))
 
# This code is contributed by Mohit Kumar

// C# program to implement the
// above approach
using System;
 
class GFG{
 
// Function to calculate and returns the
// value of Binomial Coefficient C(n, k)
static long binomialCoeff(int n, int k)
{
    long res = 1;
 
    // Since C(n, k) = C(n, n-k)
    if (k > n - k)
        k = n - k;
 
    // Calculate the value of
    // [n*(n-1)*---*(n-k+1)] / [k*(k-1)*---*1]
    for(int i = 0; i < k; ++i)
    {
        res *= (n - i);
        res /= (i + 1);
    }
    return res;
}
 
// Function to return the count of all
// binary strings having equal count of 0's
// and 1's and each prefix substring having
// frequency of 1's >= frequencies of 0's
static long countStrings(int N)
{
     
    // If N is odd
    if (N % 2 == 1)
 
        // No such strings possible
        return 0;
 
    // Otherwise
    else
    {
        N /= 2;
 
        // Calculate value of 2nCn
        long c = binomialCoeff(2 * N, N);
 
        // Return 2nCn/(n+1)
        return c / (N + 1);
    }
}
 
// Driver code
public static void Main(String[] args)
{
    int N = 6;
     
    Console.Write(countStrings(N) + " ");
}
}
 
// This code is contributed by PrinciRaj1992

<script>
// javascript program to implement the
// above approach
 
    // Function to calculate and returns the
    // value of Binomial Coefficient C(n, k)
    function binomialCoeff(n , k) {
        var res = 1;
 
        // Since C(n, k) = C(n, n-k)
        if (k > n - k)
            k = n - k;
 
        // Calculate the value of
        // [n*(n-1)*---*(n-k+1)] / [k*(k-1)*---*1]
        for (var i = 0; i < k; ++i) {
            res *= (n - i);
            res /= (i + 1);
        }
        return res;
    }
 
    // Function to return the count of all
    // binary strings having equal count of 0's
    // and 1's and each prefix substring having
    // frequency of 1's >= frequencies of 0's
    function countStrings(N) {
 
        // If N is odd
        if (N % 2 == 1)
 
            // No such strings possible
            return 0;
 
        // Otherwise
        else
        {
            N /= 2;
 
            // Calculate value of 2nCn
            var c = binomialCoeff(2 * N, N);
 
            // Return 2nCn/(n+1)
            return c / (N + 1);
        }
    }
 
    // Driver code
    var N = 6;
    document.write(countStrings(N) + " ");
 
// This code is contributed by Princi Singh
</script>

5

Complejidad temporal: O(N) 
Espacio auxiliar: O(1)