Dado un número entero N , la tarea es encontrar el número de strings binarias posibles de longitud N que tengan la misma frecuencia de 0 s y 1 s. Si tal string es posible de longitud N , imprima -1 .
Nota: dado que el conteo puede ser muy grande, devuelva la respuesta módulo 10 9 +7 .
Ejemplos:
Entrada: N = 2
Salida: 2
Explicación:
Todas las posibles strings binarias de longitud 2 son «00», «01», «10» y «11».
Entre ellos, «10» y «01» tienen la misma frecuencia de 0 y 1.
Por lo tanto, la respuesta es 2.
Entrada: 4
Salida: 6
Explicación:
Las strings «0011», «0101», «0110», «1100», «1010» y «1001» tienen la misma frecuencia de 0 y 1.
Por lo tanto, la respuesta es 6.
Enfoque ingenuo:
el enfoque más simple es generar todas las permutaciones posibles de una string de longitud N que tenga el mismo número de ‘0’ y ‘1’ . Por cada permutación generada, aumente el conteo . Imprime el recuento total de permutaciones generadas.
Complejidad de tiempo: O(N*N!)
Espacio auxiliar : O(N)
Enfoque eficiente:
El enfoque anterior se puede optimizar mediante el uso de conceptos de permutación y combinación . Siga los pasos a continuación para resolver el problema:
- Dado que N posiciones deben llenarse con el mismo número de 0 y 1 , seleccione N/2 posiciones de las N posiciones en C(N, N/2) % mod (donde mod = 10 9 + 7) formas de llenar con sólo 1’s.
- Rellene las posiciones restantes en C(N/2, N/2) % mod (es decir, 1) con solo 0.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ Program to implement
// the above approach
#include <bits/stdc++.h>
using namespace std;
#define MOD 1000000007
// Function to calculate C(n, r) % MOD
// DP based approach
int nCrModp(int n, int r)
{
// Corner case
if (n % 2 == 1) {
return -1;
}
// Stores the last row
// of Pascal's Triangle
int C[r + 1];
memset(C, 0, sizeof(C));
// Initialize top row
// of pascal triangle
C[0] = 1;
// Construct Pascal's Triangle
// from top to bottom
for (int i = 1; i <= n; i++) {
// Fill current row with the
// help of previous row
for (int j = min(i, r); j > 0;
j--)
// C(n, j) = C(n-1, j)
// + C(n-1, j-1)
C[j] = (C[j] + C[j - 1])
% MOD;
}
return C[r];
}
// Driver Code
int main()
{
int N = 6;
cout << nCrModp(N, N / 2);
return 0;
}
Java
// Java program for the above approach
import java.util.*;
class GFG{
final static int MOD = 1000000007;
// Function to calculate C(n, r) % MOD
// DP based approach
static int nCrModp(int n, int r)
{
// Corner case
if (n % 2 == 1)
{
return -1;
}
// Stores the last row
// of Pascal's Triangle
int C[] = new int[r + 1];
Arrays.fill(C, 0);
// Initialize top row
// of pascal triangle
C[0] = 1;
// Construct Pascal's Triangle
// from top to bottom
for(int i = 1; i <= n; i++)
{
// Fill current row with the
// help of previous row
for(int j = Math.min(i, r);
j > 0; j--)
// C(n, j) = C(n-1, j)
// + C(n-1, j-1)
C[j] = (C[j] + C[j - 1]) % MOD;
}
return C[r];
}
// Driver Code
public static void main(String s[])
{
int N = 6;
System.out.println(nCrModp(N, N / 2));
}
}
// This code is contributed by rutvik_56
Python3
# Python3 program to implement # the above approach MOD = 1000000007 # Function to calculate C(n, r) % MOD # DP based approach def nCrModp (n, r): # Corner case if (n % 2 == 1): return -1 # Stores the last row # of Pascal's Triangle C = [0] * (r + 1) # Initialize top row # of pascal triangle C[0] = 1 # Construct Pascal's Triangle # from top to bottom for i in range(1, n + 1): # Fill current row with the # help of previous row for j in range(min(i, r), 0, -1): # C(n, j) = C(n-1, j) # + C(n-1, j-1) C[j] = (C[j] + C[j - 1]) % MOD return C[r] # Driver Code N = 6 print(nCrModp(N, N // 2)) # This code is contributed by himanshu77
C#
// C# program for the above approach
using System;
class GFG{
static int MOD = 1000000007;
// Function to calculate C(n, r) % MOD
// DP based approach
static int nCrModp(int n, int r)
{
// Corner case
if (n % 2 == 1)
{
return -1;
}
// Stores the last row
// of Pascal's Triangle
int[] C = new int[r + 1];
// Initialize top row
// of pascal triangle
C[0] = 1;
// Construct Pascal's Triangle
// from top to bottom
for(int i = 1; i <= n; i++)
{
// Fill current row with the
// help of previous row
for(int j = Math.Min(i, r);
j > 0; j--)
// C(n, j) = C(n-1, j)
// + C(n-1, j-1)
C[j] = (C[j] + C[j - 1]) % MOD;
}
return C[r];
}
// Driver code
static void Main()
{
int N = 6;
Console.WriteLine(nCrModp(N, N / 2));
}
}
// This code is contributed by divyeshrabadiya07
Javascript
<script>
// Javascript program for the above approach
var MOD = 1000000007;
// Function to calculate C(n, r) % MOD
// DP based approach
function nCrModp(n , r) {
// Corner case
if (n % 2 == 1) {
return -1;
}
// Stores the last row
// of Pascal's Triangle
var C = Array(r + 1).fill(0);
// Initialize top row
// of pascal triangle
C[0] = 1;
// Construct Pascal's Triangle
// from top to bottom
for (i = 1; i <= n; i++) {
// Fill current row with the
// help of previous row
for (j = Math.min(i, r); j > 0; j--)
// C(n, j) = C(n-1, j)
// + C(n-1, j-1)
C[j] = (C[j] + C[j - 1]) % MOD;
}
return C[r];
}
// Driver Code
var N = 6;
document.write(nCrModp(N, N / 2));
// This code contributed by gauravrajput1
</script>
20
Complejidad de tiempo: O(N 2 )
Complejidad de espacio: O(N)
Publicación traducida automáticamente
Artículo escrito por math_lover y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA