Given two integers M and X, the task is to find the number of sequences of length M that can be generated comprising X and -X such that their respective counts are equal and the prefix sum up to each index of the resulting sequence is non-negative.
Examples:
Input: M = 4, X = 5
Output: 2
Explanation:
There are only 2 possible sequences that have all possible prefix sums non-negative:
- {+5, +5, -5, -5}
- {+5, -5, +5, -5}
Input: M = 6, X = 2
Output: 5
Explanation:
There are only 5 possible sequences that have all possible prefix sums non-negative:
- {+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}
Naive Approach: The simplest approach is to generate all possible arrangements of size M with the given integers +X and -X and find the prefix sum of each arrangement formed and count those sequences whose prefix sum array has only non-negative elements. Print the count of such sequence after the above steps.
Time Complexity: O((M*(M!))/((M/2)!)2)
Auxiliary Space: O(M)
Efficient Approach: The idea is to observe the pattern that for any sequence formed the number of positive X that has occurred at each index is always greater than or equal to the number of negative X that occurred. This is similar to the pattern of Catalan Numbers. In this case, check that at any point the number of positive X that occurred is always greater than or equal to the number of negative X that occurred which is the pattern of Catalan numbers. So the task is to find the Nth Catalan number where N = M/2.
where, KN is Nth the Catalan Number and
is the binomial coefficient.
is the binomial coefficient. Below is the implementation of the above approach:
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-negativevoid 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 Codeint main(){ // Given M and X int M = 4, X = 5; // Function Call findWays(M); return 0;} |
Java
// Java program for the above approachimport 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-negativestatic 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 Codepublic 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-negativedef 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 Codeif __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 approachusing 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-negativestatic 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 Codepublic 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-negativefunction 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
Time Complexity: O(M)
Auxiliary Space: O(1)
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
