Given an integer N, the task is to find the number of distinct bracket sequences that can be formed using 2 * N brackets such that the sequence is not N-periodic.
A bracket sequence str of length 2 * N is said to be N-periodic if the sequence can be split into two equal substrings having same regular bracket sequence.
A regular bracket sequence is a sequence in the following way:
- An empty string is a regular bracket sequence.
- If s & t are regular bracket sequences, then s + t is a regular bracket sequence.
Examples:
Input: N = 3
Output: 5
Explanation:
There will be 5 distinct regular bracket sequences of length 2 * N = ()()(), ()(()), (())(), (()()), ((()))
Now, none of the sequences are N-periodic. Therefore, the output is 5.Input: N = 4
Output: 12
Explanation:
There will be 14 distinct regular bracket sequences of length 2*N which are
()()()(), ()()(()), ()(())(), ()(()()), ()((())), (())()(), (())(()), (()())(), (()()()), (()(())), ((()))(), ((())()), ((()())), (((())))
Out of these 14 regular sequences, two of them are N periodic which are
()()()() and (())(()). They have a period of N.
Therefore, the distinct regular bracket sequences of length 2 * N which are not N-periodic are 14 – 2 = 12.
Approach: The idea is to calculate the total number of regular bracket sequences possible of length 2 * N and then to subtract the number of bracket sequences which are N-periodic from it. Below are the steps:
- To find the number of regular bracket sequences of length 2*N, use the Catalan number formula.
- For a sequence of length 2*N to be N periodic, N should be even because if N is odd then the sequence of length 2*N cannot be a regular sequence and have a period of N at the same time.
- Since the concatenation of two similar non-regular bracket sequences cannot make a sequence regular, so both subsequences of length N should be regular.
- Reduce the number of regular bracket sequences of length N(if N is even) from the number of regular bracket sequences of length 2*N to get the desired result.
Below is the implementation of the above approach:
C++
// C++ program for the above approach#include <bits/stdc++.h>using namespace std;// Function that finds the value of// Binomial Coefficient C(n, k)unsigned long intbinomialCoeff(unsigned int n, unsigned int k){ unsigned long int res = 1; // Since C(n, k) = C(n, n - k) if (k > n - k) k = n - k; // Calculate the value of // [n*(n - 1)*---*(n - k + 1)] / // [k*(k - 1)*---*1] for (int i = 0; i < k; ++i) { res *= (n - i); res /= (i + 1); } // Return the C(n, k) return res;}// Binomial coefficient based function to// find nth catalan number in O(n) timeunsigned long int catalan(unsigned int n){ // Calculate value of 2nCn unsigned long int c = binomialCoeff(2 * n, n); // Return C(2n, n)/(n+1) return c / (n + 1);}// Function to find possible ways to// put balanced parenthesis in an// expression of length nunsigned long int findWays(unsigned n){ // If n is odd, not possible to // create any valid parentheses if (n & 1) return 0; // Otherwise return n/2th // Catalan Number return catalan(n / 2);}void countNonNPeriodic(int N){ // Difference between counting ways // of 2*N and N is the result cout << findWays(2 * N) - findWays(N);}// Driver Codeint main(){ // Given value of N int N = 4; // Function Call countNonNPeriodic(N); return 0;} |
Java
// Java program for above approachimport java.io.*;class GFG{ // Function that finds the value of // Binomial Coefficient C(n, k) static long binomialCoeff(int n, int k) { long res = 1; // Since C(n, k) = C(n, n - k) if (k > n - k) k = n - k; // Calculate the value of // [n*(n - 1)*---*(n - k + 1)] / // [k*(k - 1)*---*1] for(int i = 0; i < k; ++i) { res *= (n - i); res /= (i + 1); } // Return the C(n, k) return res; } // Binomial coefficient based function to // find nth catalan number in O(n) time static long catalan(int n) { // Calculate value of 2nCn long c = binomialCoeff(2 * n, n); // Return C(2n, n)/(n+1) return c / (n + 1); } // Function to find possible ways to // put balanced parenthesis in an // expression of length n static long findWays(int n) { // If n is odd, not possible to // create any valid parentheses if ((n & 1) == 1) return 0; // Otherwise return n/2th // Catalan Number return catalan(n / 2); } static void countNonNPeriodic(int N) { // Difference between counting ways // of 2*N and N is the result System.out.println(findWays(2 * N) - findWays(N)); }// Driver codepublic static void main (String[] args){ // Given value of N int N = 4; // Function call countNonNPeriodic(N); }}// This code is contributed by offbeat |
Python3
# Python3 program for # the above approach# Function that finds the value of # Binomial Coefficient C(n, k) def binomialCoeff(n, k): res = 1 # Since C(n, k) = C(n, n - k) if (k > n - k): k = n - k # Calculate the value of # [n*(n - 1)*---*(n - k + 1)] / # [k*(k - 1)*---*1] for i in range(k): res = res * (n - i) res = res // (i + 1) # Return the C(n, k) return res # Binomial coefficient based function to # find nth catalan number in O(n) time def catalan(n): # Calculate value of 2nCn c = binomialCoeff(2 * n, n) # Return C(2n, n)/(n+1) return c // (n + 1) # Function to find possible ways to # put balanced parenthesis in an # expression of length n def findWays(n): # If n is odd, not possible to # create any valid parentheses if ((n & 1) == 1): return 0 # Otherwise return n/2th # Catalan Number return catalan(n // 2) def countNonNPeriodic(N): # Difference between counting ways # of 2*N and N is the result print(findWays(2 * N) - findWays(N)) # Driver code# Given value of N N = 4 # Function call countNonNPeriodic(N) # This code is contributed by divyeshrabadiya07 |
C#
// C# program for above approach using System; using System.Collections.Generic; class GFG{ // Function that finds the value of // Binomial Coefficient C(n, k) static long binomialCoeff(int n, int k) { long res = 1; // Since C(n, k) = C(n, n - k) if (k > n - k) k = n - k; // Calculate the value of // [n*(n - 1)*---*(n - k + 1)] / // [k*(k - 1)*---*1] for(int i = 0; i < k; ++i) { res *= (n - i); res /= (i + 1); } // Return the C(n, k) return res; } // Binomial coefficient based function to // find nth catalan number in O(n) time static long catalan(int n) { // Calculate value of 2nCn long c = binomialCoeff(2 * n, n); // Return C(2n, n)/(n+1) return c / (n + 1); } // Function to find possible ways to // put balanced parenthesis in an // expression of length n static long findWays(int n) { // If n is odd, not possible to // create any valid parentheses if ((n & 1) == 1) return 0; // Otherwise return n/2th // Catalan Number return catalan(n / 2); } static void countNonNPeriodic(int N) { // Difference between counting ways // of 2*N and N is the result Console.Write(findWays(2 * N) - findWays(N)); } // Driver Code public static void Main(string[] args) { // Given value of N int N = 4; // Function call countNonNPeriodic(N);} } // This code is contributed by rutvik_56 |
Javascript
<script>// Javascript program for the above approach// Function that finds the value of// Binomial Coefficient C(n, k)function binomialCoeff(n, k){ let res = 1; // Since C(n, k) = C(n, n - k) if (k > n - k) k = n - k; // Calculate the value of // [n*(n - 1)*---*(n - k + 1)] / // [k*(k - 1)*---*1] for (let i = 0; i < k; ++i) { res *= (n - i); res /= (i + 1); } // Return the C(n, k) return res;}// Binomial coefficient based function to// find nth catalan number in O(n) timefunction catalan(n){ // Calculate value of 2nCn let c = binomialCoeff(2 * n, n); // Return C(2n, n)/(n+1) return c / (n + 1);}// Function to find possible ways to// put balanced parenthesis in an// expression of length nfunction findWays(n){ // If n is odd, not possible to // create any valid parentheses if (n & 1) return 0; // Otherwise return n/2th // Catalan Number return catalan(n / 2);}function countNonNPeriodic(N){ // Difference between counting ways // of 2*N and N is the result document.write(findWays(2 * N) - findWays(N));}// Driver Code // Given value of N let N = 4; // Function Call countNonNPeriodic(N);// This code is contributed by Mayank Tyagi</script> |
Output:
12
Time Complexity: O(N)
Auxiliary Space: O(1)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
