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

Dados los números enteros positivos N , X e Y . La tarea es encontrar el conteo de strings binarias únicas de longitud N que tengan X 0 e Y 1 s.

Ejemplos:

Entrada: N=5, X=3, Y=2
Salida: 10
Explicación: Hay 10 strings binarias de longitud 5 con 3 0 y 2 1, como: 
00011, 00101, 01001, 10001, 00110, 01010, 10010, 01100, 10100, 11000.

Entrada: N=3, X=1, Y=2
Salida: 3
Explicación: Hay 3 strings binarias de longitud 3 con 1 0 y 2 1, como: 011, 101, 110

Enfoque ingenuo : genere todas las strings binarias de longitud N y luego cuente el número de strings con X 0 e Y 1.
Complejidad de Tiempo: O(2 ^N )
Espacio Auxiliar: O(2 ^N )

Mejor enfoque : este problema también se puede resolver usando combinatoria . Si la longitud es N, y dado X 0s, entonces habrá Y = (N – X) 1s. Entonces podemos pensar en esto como una string de longitud N con X 0 e Y 1. Necesitamos encontrar el número de combinaciones únicas para esto, que se pueden obtener como _ {X}^{N}\textrm{C} o _ {Y}^{N}\textrm{C}. Esto se puede hacer usando el triángulo de Pascal para calcular el valor de la combinación.
Complejidad de tiempo: O(N) 
Complejidad de espacio: O(N ² )
Nota: Este enfoque es el mejor si hay múltiples consultas para X e Y. Entonces también tendrá la misma complejidad de tiempo y espacio.

Enfoque de espacio optimizado : el consumo de espacio en el enfoque anterior se puede optimizar si tomamos la ayuda de la fórmula _ {X}^{N}\textrm{C} = N!/(X!*(NX)!) y calculamos el valor usando los factoriales.

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

#include <bits/stdc++.h>
using namespace std;
 
// Function to calculate factorial
long long int fact(int f)
{
    f++;
    long long int ans = 1;
 
    // Loop to calculate factorial of f
    while (--f > 0)
        ans = ans * f;
    return ans;
}
 
// Function to calculate combination nCr
long long int countWays(int N, int X, int Y)
{
    return (fact(N) / (fact(X) * fact(Y)));
}
 
// Driver code
int main()
{
    int N = 5, X = 3, Y = 2;
    cout << countWays(N, X, Y) << endl;
    return 0;
}

// Java program for the above approach
public class GFG{
 
    // Function to calculate factorial
    static int fact(int f)
    {
        f++;
        int ans = 1;
     
        // Loop to calculate factorial of f
        while (--f > 0)
            ans = ans * f;
        return ans;
    }
 
    // Function to calculate combination nCr
    static int countWays(int N, int X, int Y)
    {
        return (fact(N) / (fact(X) * fact(Y)));
    }
 
    // Driver Code
    public static void main(String args[])
    {
        int N = 5, X = 3, Y = 2;
        System.out.println(countWays(N, X, Y));
    }
}
 
// This code is contributed by AnkThon

# Function to calculate factorial
def fact(f):
  ans = 1;
 
  # Loop to calculate factorial of f
  while (f):
    ans = ans * f;
    f -= 1
 
  return ans;
 
# Function to calculate combination nCr
def countWays(N, X, Y):
  return fact(N) // (fact(X) * fact(Y));
 
 
# Driver code
N = 5
X = 3
Y = 2
print(countWays(N, X, Y))
 
# This code is contributed by gfgking

// C# program for the above approach
using System;
using System.Collections.Generic;
 
class GFG{
 
// Function to calculate factorial
static int fact(int f)
{
    f++;
    int ans = 1;
 
    // Loop to calculate factorial of f
    while (--f > 0)
        ans = ans * f;
    return ans;
}
 
// Function to calculate combination nCr
static int countWays(int N, int X, int Y)
{
    return (fact(N) / (fact(X) * fact(Y)));
}
 
 
// Driver Code
public static void Main()
{
    int N = 5, X = 3, Y = 2;
    Console.Write(countWays(N, X, Y));
}
}
 
// This code is contributed by sanjoy_62.

<script>
// Function to calculate factorial
function fact(f) {
  f++;
  let ans = 1;
 
  // Loop to calculate factorial of f
  while (--f > 0)
    ans = ans * f;
  return ans;
}
 
// Function to calculate combination nCr
function countWays(N, X, Y) {
  return Math.floor(fact(N) / (fact(X) * fact(Y)));
}
 
// Driver code
let N = 5, X = 3, Y = 2;
document.write(countWays(N, X, Y))
 
// This code is contributed by saurabh_jaiswal.
</script>

10

Complejidad de tiempo: O(N)
Espacio auxiliar: O(1)
Nota: En caso de consultas múltiples (Q), este enfoque tendrá una complejidad de tiempo O(Q*N).