Count distinct regular bracket sequences which are not N periodic

0 0 7 minutes read

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 int
binomialCoeff(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) time
unsigned 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 n
unsigned 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 Code
int main()
{
    // Given value of N
    int N = 4;
 
    // Function Call
    countNonNPeriodic(N);
 
    return 0;
}

Java

// Java program for above approach
import 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 code
public 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) time
function 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 n
function 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:

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 zambiatek!