Recuento de strings binarias de longitud N con al menos X 0 e Y 1

Dados tres números N, X e Y , encuentre el recuento de strings binarias únicas de longitud N que tengan al menos X 0 e Y 1 .

Ejemplos :

Entrada: N=5, X=1, Y=2
Salida: 25

Entrada: N=3, X=1, Y=1
Salida: 6
Explicación: Hay 3 strings binarias de longitud 3 con al menos 1 0 y 1 1, como: 001, 010, 100, 011, 101, 110

Enfoque ingenuo: genere todas las strings binarias de longitud N y luego cuente la cantidad de strings con al menos X 0 e Y 1 .
Complejidad de tiempo: O(2^N)
Espacio auxiliar: O(1)

Mejor enfoque: este problema también se puede resolver usando combinatoria . Si la longitud es N , y dado X 0s , entonces habrá Y (=NX) 1s . Entonces, necesitamos encontrar el número de combinaciones únicas para esto, que se pueden obtener como (N) C (X) o (N) C (Y). Ahora, para todas las strings binarias únicas, necesitamos encontrar el nCi para los valores de i en el rango [X, NY] y agregarlo a una variable. El valor de esta suma después de todas las iteraciones será el conteo requerido.

Enfoque eficiente: el enfoque anterior se puede optimizar aún más con la ayuda del triángulo de Pascal para calcular nCr . Siga los pasos a continuación para resolver el problema:

• Inicialice la array 2-D p[][] para calcular usando el triángulo pascal.
• Inicialice la suma variable como 0 para almacenar la respuesta.
• Iterar sobre el rango [x, ny] usando la variable i y realizar las siguientes tareas:
  • Agregue el valor p[n][i] a la variable sum .
• Después de realizar los pasos anteriores, imprima el valor de sum como respuesta.

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

// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
 
long long int p[31][31];
 
// Function to use pascal triangle
void pascalTriangle()
{
    p[0][0] = 1;
    p[1][0] = 1;
    p[1][1] = 1;
    for (int i = 2; i < 31; i++) {
        p[i][0] = 1;
        for (int j = 1; j < i; j++)
            p[i][j] = p[i - 1][j]
                      + p[i - 1][j - 1];
        p[i][i] = 1;
    }
}
 
// Function to count the total number of ways
long long int countWays(int n, int x, int y)
{
 
    // Store the answer
    long long int sum = 0;
 
    // Traverse
    for (long long int i = x; i <= n - y; i++) {
        sum += p[n][i];
    }
    return sum;
}
 
// Driver Code
int main()
{
    pascalTriangle();
 
    int N = 5, X = 1, Y = 2;
    cout << countWays(N, X, Y) << endl;
 
    return 0;
}

// Java code for the above approach
import java.io.*;
class GFG {
 
    static int[][] p = new int[31][31];
 
    // Function to use pascal triangle
    static void pascalTriangle()
    {
        p[0][0] = 1;
        p[1][0] = 1;
        p[1][1] = 1;
        for (int i = 2; i < 31; i++) {
            p[i][0] = 1;
            for (int j = 1; j < i; j++)
                p[i][j] = p[i - 1][j] + p[i - 1][j - 1];
            p[i][i] = 1;
        }
    }
 
    // Function to count the total number of ways
    static long countWays(int n, int x, int y)
    {
 
        // Store the answer
        long sum = 0;
 
        // Traverse
        for (int i = x; i <= n - y; i++) {
            sum += p[n][i];
        }
        return sum;
    }
 
    // Driver Code
    public static void main(String[] args)
    {
        pascalTriangle();
 
        int N = 5;
        int X = 1;
        int Y = 2;
 
        System.out.println(countWays(N, X, Y));
    }
}
 
// This code is contributed by Potta Lokesh

# Python program for the above approach
p = [[0 for i in range(31)] for i in range(31)]
 
# Function to use pascal triangle
def pascalTriangle():
    p[0][0] = 1
    p[1][0] = 1
    p[1][1] = 1
    for i in range(2, 31):
        p[i][0] = 1
        for j in range(1, i):
            p[i][j] = p[i - 1][j] + p[i - 1][j - 1]
        p[i][i] = 1
 
# Function to count the total number of ways
def countWays(n, x, y):
 
    # Store the answer
    sum = 0
 
    # Traverse
    for i in range(x, n - y + 1):
        sum += p[n][i]
    return sum
 
# Driver Code
pascalTriangle()
 
N = 5
X = 1
Y = 2
print(countWays(N, X, Y))
 
# This code is contributed by gfgking

// C# code for the above approach
using System;
 
public class GFG {
 
    static int[,] p = new int[31,31];
 
    // Function to use pascal triangle
    static void pascalTriangle()
    {
        p[0,0] = 1;
        p[1,0] = 1;
        p[1,1] = 1;
        for (int i = 2; i < 31; i++) {
            p[i,0] = 1;
            for (int j = 1; j < i; j++)
                p[i,j] = p[i - 1,j] + p[i - 1,j - 1];
            p[i,i] = 1;
        }
    }
 
    // Function to count the total number of ways
    static long countWays(int n, int x, int y)
    {
 
        // Store the answer
        long sum = 0;
 
        // Traverse
        for (int i = x; i <= n - y; i++) {
            sum += p[n,i];
        }
        return sum;
    }
 
    // Driver Code
    public static void Main(String[] args)
    {
        pascalTriangle();
 
        int N = 5;
        int X = 1;
        int Y = 2;
 
        Console.WriteLine(countWays(N, X, Y));
    }
}
 
// This code is contributed by 29AjayKumar

<script>
    // JavaScript program for the above approach
 
    let p = new Array(31).fill(0).map(() => new Array(31).fill(0));
 
    // Function to use pascal triangle
    const pascalTriangle = () => {
        p[0][0] = 1;
        p[1][0] = 1;
        p[1][1] = 1;
        for (let i = 2; i < 31; i++) {
            p[i][0] = 1;
            for (let j = 1; j < i; j++)
                p[i][j] = p[i - 1][j]
                    + p[i - 1][j - 1];
            p[i][i] = 1;
        }
    }
 
    // Function to count the total number of ways
    const countWays = (n, x, y) => {
 
        // Store the answer
        let sum = 0;
 
        // Traverse
        for (let i = x; i <= n - y; i++) {
            sum += p[n][i];
        }
        return sum;
    }
 
    // Driver Code
 
    pascalTriangle();
 
    let N = 5, X = 1, Y = 2;
    document.write(countWays(N, X, Y));
 
// This code is contributed by rakeshsahni
 
</script>

25

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