Dados dos enteros M y X , la tarea es encontrar el número de secuencias de longitud M que se pueden generar que comprendan X y -X de modo que sus respectivos recuentos sean iguales y el prefijo que suma a cada índice de la secuencia resultante no sea negativo _
Ejemplos:
Entrada: M = 4, X = 5
Salida: 2
Explicación:
Solo hay 2 secuencias posibles que tienen todas las sumas de prefijos posibles no negativas:
- {+5, +5, -5, -5}
- {+5, -5, +5, -5}
Entrada: M = 6, X = 2
Salida: 5
Explicación:
Solo hay 5 secuencias posibles que tienen todas las sumas de prefijos posibles no negativas:
- {+2, +2, +2, -2, -2, -2}
- {+2, +2, -2, -2, +2, -2}
- {+2, -2, +2, -2, +2, -2}
- {+2, +2, -2, +2, -2, -2}
- {+2, -2, +2, +2, -2, -2}
Enfoque ingenuo : el enfoque más simple es generar todos los arreglos posibles de tamaño M con los números enteros +X y -X dados y encontrar la suma de prefijos de cada arreglo formado y contar aquellas secuencias cuya array de suma de prefijos tiene solo elementos no negativos. Imprima el recuento de dicha secuencia después de los pasos anteriores.
Complejidad de tiempo: O((M*(M!))/((M/2)!) 2 )
Espacio auxiliar: O(M)
Enfoque eficiente : la idea es observar el patrón de que, para cualquier secuencia formada, el número de X positivas que se han producido en cada índice es siempre mayor o igual que el número de X negativas que se han producido. Esto es similar al patrón de los números catalanes . En este caso, compruebe que en cualquier punto el número de X positivas que se produjeron es siempre mayor o igual que el número de X negativas que se produjeron, que es el patrón de los números catalanes. Entonces, la tarea es encontrar el N- ésimo número catalán donde N = M/2 .
donde, K N es N el Número Catalán y
es el coeficiente binomial.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
// Function to find the Binomial
// Coefficient C(n, r)
unsigned long int binCoff(unsigned int n,
unsigned int r)
{
// Stores the value C(n, r)
unsigned long int val = 1;
int i;
// Update C(n, r) = C(n, n - r)
if (r > (n - r))
r = (n - r);
// Find C(n, r) iteratively
for (i = 0; i < r; i++) {
val *= (n - i);
val /= (i + 1);
}
// Return the final value
return val;
}
// Function to find number of sequence
// whose prefix sum at each index is
// always non-negative
void findWays(int M)
{
// Find n
int n = M / 2;
unsigned long int a, b, ans;
// Value of C(2n, n)
a = binCoff(2 * n, n);
// Catalan number
b = a / (n + 1);
// Print the answer
cout << b;
}
// Driver Code
int main()
{
// Given M and X
int M = 4, X = 5;
// Function Call
findWays(M);
return 0;
}
Java
// Java program for the above approach
import java.io.*;
class GFG{
// Function to find the Binomial
// Coefficient C(n, r)
static long binCoff(long n, long r)
{
// Stores the value C(n, r)
long val = 1;
int i;
// Update C(n, r) = C(n, n - r)
if (r > (n - r))
r = (n - r);
// Find C(n, r) iteratively
for(i = 0; i < r; i++)
{
val *= (n - i);
val /= (i + 1);
}
// Return the final value
return val;
}
// Function to find number of sequence
// whose prefix sum at each index is
// always non-negative
static void findWays(int M)
{
// Find n
int n = M / 2;
long a, b, ans;
// Value of C(2n, n)
a = binCoff(2 * n, n);
// Catalan number
b = a / (n + 1);
// Print the answer
System.out.print(b);
}
// Driver Code
public static void main(String[] args)
{
// Given M and X
int M = 4, X = 5;
// Function Call
findWays(M);
}
}
// This code is contributed by akhilsaini
Python3
# Python3 program for the above approach # Function to find the Binomial # Coefficient C(n, r) def binCoff(n, r): # Stores the value C(n, r) val = 1 # Update C(n, r) = C(n, n - r) if (r > (n - r)): r = (n - r) # Find C(n, r) iteratively for i in range(0, r): val *= (n - i) val //= (i + 1) # Return the final value return val # Function to find number of sequence # whose prefix sum at each index is # always non-negative def findWays(M): # Find n n = M // 2 # Value of C(2n, n) a = binCoff(2 * n, n) # Catalan number b = a // (n + 1) # Print the answer print(b) # Driver Code if __name__ == '__main__': # Given M and X M = 4 X = 5 # Function Call findWays(M) # This code is contributed by akhilsaini
C#
// C# program for the above approach
using System;
class GFG{
// Function to find the Binomial
// Coefficient C(n, r)
static long binCoff(long n, long r)
{
// Stores the value C(n, r)
long val = 1;
int i;
// Update C(n, r) = C(n, n - r)
if (r > (n - r))
r = (n - r);
// Find C(n, r) iteratively
for(i = 0; i < r; i++)
{
val *= (n - i);
val /= (i + 1);
}
// Return the final value
return val;
}
// Function to find number of sequence
// whose prefix sum at each index is
// always non-negative
static void findWays(int M, int X)
{
// Find n
int n = M / 2;
long a, b;
// Value of C(2n, n)
a = binCoff(2 * n, n);
// Catalan number
b = a / (n + 1);
// Print the answer
Console.WriteLine(b);
}
// Driver Code
public static void Main()
{
// Given M and X
int M = 4;
int X = 5;
// Function Call
findWays(M, X);
}
}
// This code is contributed by akhilsaini
Javascript
<script>
// Javascript program to implement
// the above approach
// Function to find the Binomial
// Coefficient C(n, r)
function binCoff(n, r)
{
// Stores the value C(n, r)
let val = 1;
let i;
// Update C(n, r) = C(n, n - r)
if (r > (n - r))
r = (n - r);
// Find C(n, r) iteratively
for(i = 0; i < r; i++)
{
val *= (n - i);
val /= (i + 1);
}
// Return the final value
return val;
}
// Function to find number of sequence
// whose prefix sum at each index is
// always non-negative
function findWays(M)
{
// Find n
let n = M / 2;
let a, b, ans;
// Value of C(2n, n)
a = binCoff(2 * n, n);
// Catalan number
b = a / (n + 1);
// Print the answer
document.write(b);
}
// Driver Code
// Given M and X
let M = 4, X = 5;
// Function Call
findWays(M);
</script>
2
Tiempo Complejidad: O(M)
Espacio Auxiliar: O(1)
Publicación traducida automáticamente
Artículo escrito por shashanktrivedi02 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA