Cuente strings binarias con dos veces ceros en la primera mitad

Nos dan un número entero N. Necesitamos contar el número total de tales strings binarias de longitud N tal que el número de ‘0’s en la primera string de longitud N/2 es el doble del número de ‘0’s en la segunda string de longitud N/2.
Nota: N es siempre un número entero positivo par.
Ejemplos:

Entrada: N = 4
Salida: 2
Explicación: 0010 y 0001 son dos strings binarias tales que el número de ceros en la primera mitad es el doble del número de ceros en la segunda mitad.

Entrada: N = 6
Salida: 9

Enfoque ingenuo: podemos generar toda la string binaria de longitud N y luego, una por una, podemos verificar si la string seleccionada sigue el escenario dado. Pero la complejidad del tiempo para este enfoque es exponencial y es O(N*2 ^N ).
Enfoque eficiente: este enfoque se basa en un análisis matemático del problema.
Requisito previo para este enfoque: factorial y combinatoria con función de módulo.
Nota: Sea n = N/2.
Si realizamos un análisis paso a paso:

El número de strings que contienen dos ‘0’ en la primera mitad de la string y un ‘0’ en la segunda mitad de la string es igual a ⁿ C ₂ * ⁿ C ₁ .
El número de strings que contienen cuatro ‘0’ en la primera mitad de la string y dos ‘0’ en la segunda mitad de la string, es igual a ⁿ C ₄ * ⁿ C ₂ .
El número de strings que contienen seis ‘0’ en la primera mitad de la string y tres ‘0’ en la segunda mitad de la string es igual a ⁿ C ₆ * ⁿ C ₃ .

Repetimos el procedimiento anterior hasta que el número de ‘0’ en la primera mitad se convierta en n si n es par o (n-1) si n es impar.
Entonces, nuestra respuesta final es Σ ( ⁿ C _(2*i) * ⁿ C _i ) , para 2 <= 2*i <= n.
Ahora, podemos calcular el número requerido de strings simplemente usando Permutación y Combinación.
Algoritmo:

int n = N/2;
for(int i=2;i<=n;i=i+2)
             ans += ( nCr(n, i) * nCr(n, i/2);

Nota: puede utilizar la técnica de programación dinámica para precalcular CoeFunc(N, i) ie ⁿ C _i .
La complejidad del tiempo es O(N) si calculamos previamente CoeFunc(N, i) en O(N*N).

C++

// CPP for finding number of binary strings
// number of '0' in first half is double the
// number of '0' in second half of string
#include <bits/stdc++.h>
 
// pre define some constant
#define mod 1000000007
#define max 1001
using namespace std;
 
// global values for pre computation
long long int nCr[1003][1003];
 
void preComputeCoeff()
{
    for (int i = 0; i < max; i++) {
        for (int j = 0; j <= i; j++) {
            if (j == 0 || j == i)
                nCr[i][j] = 1;
            else
                nCr[i][j] = (nCr[i - 1][j - 1] +
                             nCr[i - 1][j]) % mod;
        }
    }
}
 
// function to print number of required string
long long int computeStringCount(int N)
{
    int n = N / 2;
    long long int ans = 0;
 
    // calculate answer using proposed algorithm
    for (int i = 2; i <= n; i += 2)
        ans = (ans + ((nCr[n][i] * nCr[n][i / 2])
                      % mod)) % mod;
    return ans;
}
 
// Driver code
int main()
{
    preComputeCoeff();
    int N = 3;
    cout << computeStringCount(N) << endl;
    return 0;
}

Java

// Java program for finding number of binary strings
// number of '0' in first half is double the
// number of '0' in second half of string
class GFG {
     
    // pre define some constant
    static final long mod = 1000000007;
    static final long max = 1001;
     
    // global values for pre computation
    static long nCr[][] = new long[1003][1003];
     
    static void preComputeCoeff()
    {
        for (int i = 0; i < max; i++) {
            for (int j = 0; j <= i; j++) {
                if (j == 0 || j == i)
                    nCr[i][j] = 1;
                else
                    nCr[i][j] = (nCr[i - 1][j - 1] +
                                nCr[i - 1][j]) % mod;
            }
        }
    }
     
    // function to print number of required string
    static long computeStringCount(int N)
    {
        int n = N / 2;
        long ans = 0;
     
        // calculate answer using proposed algorithm
        for (int i = 2; i <= n; i += 2)
            ans = (ans + ((nCr[n][i] * nCr[n][i / 2])
                        % mod)) % mod;
        return ans;
    }
     
    // main function
    public static void main(String[] args)
    {
        preComputeCoeff();
        int N = 3;
        System.out.println( computeStringCount(N) );
         
    }
}
 
// This code is contributed by Arnab Kundu.

Python3

# Python3 for finding number of binary strings
# number of '0' in first half is double the
# number of '0' in second half of string
 
# pre define some constant
mod = 1000000007
Max = 1001
 
# global values for pre computation
nCr = [[0 for _ in range(1003)]
          for i in range(1003)]
 
def preComputeCoeff():
 
    for i in range(Max):
        for j in range(i + 1):
            if (j == 0 or j == i):
                nCr[i][j] = 1
            else:
                nCr[i][j] = (nCr[i - 1][j - 1] +
                             nCr[i - 1][j]) % mod
         
# function to print number of required string
def computeStringCount(N):
    n = N // 2
    ans = 0
 
    # calculate answer using proposed algorithm
    for i in range(2, n + 1, 2):
        ans = (ans + ((nCr[n][i] *
                       nCr[n][i // 2]) % mod)) % mod
    return ans
 
# Driver code
preComputeCoeff()
N = 3
print(computeStringCount(N))
 
# This code is contributed by mohit kumar

C#

// C# program for finding number of binary
// strings number of '0' in first half is
// double the number of '0' in second half
// of string
using System;
 
class GFG {
     
    // pre define some constant
    static long mod = 1000000007;
    static long max = 1001;
     
    // global values for pre computation
    static long [,]nCr = new long[1003,1003];
     
    static void preComputeCoeff()
    {
        for (int i = 0; i < max; i++)
        {
            for (int j = 0; j <= i; j++)
            {
                if (j == 0 || j == i)
                    nCr[i,j] = 1;
                else
                    nCr[i,j] = (nCr[i - 1,j - 1]
                          + nCr[i - 1,j]) % mod;
            }
        }
    }
     
    // function to print number of required
    // string
    static long computeStringCount(int N)
    {
        int n = N / 2;
        long ans = 0;
     
        // calculate answer using proposed
        // algorithm
        for (int i = 2; i <= n; i += 2)
            ans = (ans + ((nCr[n,i]
                * nCr[n,i / 2]) % mod)) % mod;
                 
        return ans;
    }
     
    // main function
    public static void Main()
    {
        preComputeCoeff();
        int N = 3;
        Console.Write( computeStringCount(N) );
         
    }
}
 
// This code is contributed by nitin mittal.

Javascript

<script>
 
 
// Javascript for finding number of binary strings
// number of '0' in first half is double the
// number of '0' in second half of string
 
// pre define some constant
var mod = 1000000007
var max = 1001
 
// global values for pre computation
var nCr = Array.from(Array(1003), ()=> Array(1003));
 
function preComputeCoeff()
{
    for (var i = 0; i < max; i++) {
        for (var j = 0; j <= i; j++) {
            if (j == 0 || j == i)
                nCr[i][j] = 1;
            else
                nCr[i][j] = (nCr[i - 1][j - 1] +
                             nCr[i - 1][j]) % mod;
        }
    }
}
 
// function to print number of required string
function computeStringCount(N)
{
    var n = N / 2;
    var ans = 0;
 
    // calculate answer using proposed algorithm
    for (var i = 2; i <= n; i += 2)
        ans = (ans + ((nCr[n][i] * nCr[n][i / 2])
                      % mod)) % mod;
    return ans;
}
 
// Driver code
preComputeCoeff();
var N = 3;
document.write( computeStringCount(N));
 
// This code is contributed by noob2000.
</script>

Producción:

Publicación traducida automáticamente

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

C++

Java

Python3

C#

Javascript

Deja una respuesta Cancelar la respuesta