C++ Find Nth Catalan Number

Catalan numbers are a sequence of natural numbers that occurs in many interesting counting problems like following.
1) Count the number of expressions containing n pairs of parentheses which are correctly matched. For n = 3, possible expressions are ((())), ()(()), ()()(), (())(), (()()).
2) Count the number of possible Binary Search Trees with n keys
3) Count the number of full binary trees (A rooted binary tree is full if every vertex has either two children or no children) with n+1 leaves.
4) Given a number n, return the number of ways you can draw n chords in a circle with 2 x n points such that no 2 chords intersect.

The first few Catalan numbers for n = 0, 1, 2, 3, %u2026 are 1, 1, 2, 5, 14, 42, 132, 429, 1430, 4862, %u2026

Recursive Solution
Catalan numbers satisfy the following recursive formula.

$C_0=1 and C_n_+_1=sum_{i=0}^{n}C_iC_n_-_i for ngeq 0;$

Following is the implementation of above recursive formula.

#include <iostream> 
using namespace std; 
  
// A recursive function to find nth catalan number 
unsigned long int catalan(unsigned int n) 
{ 
    // Base case 
    if (n <= 1) 
        return 1; 
  
    // catalan(n) is sum of  
    // catalan(i)*catalan(n-i-1) 
    unsigned long int res = 0; 
    for (int i = 0; i < n; i++) 
        res += catalan(i)  
            * catalan(n - i - 1); 
  
    return res; 
} 
  
// Driver code 
int main() 
{ 
    for (int i = 0; i < 10; i++) 
        cout << catalan(i) << " "; 
    return 0; 
}

Output

1 1 2 5 14 42 132 429 1430 4862

Time complexity of above implementation is equivalent to nth catalan number.

$T(n)=sum_{i=0}^{n-1}T(i)*T(n-i-1) for ngeq 1;$

The value of nth catalan number is exponential that makes the time complexity exponential.

Dynamic Programming Solution : We can observe that the above recursive implementation does a lot of repeated work (we can the same by drawing recursion tree). Since there are overlapping subproblems, we can use dynamic programming for this. Following is a Dynamic programming based implementation .

using namespace std; 
#include <iostream>
  
// A dynamic programming based function to find nth 
// Catalan number 
unsigned long int catalanDP(unsigned int n) 
{ 
    // Table to store results of subproblems 
    unsigned long int catalan[n + 1]; 
  
    // Initialize first two values in table 
    catalan[0] = catalan[1] = 1; 
  
    // Fill entries in catalan[] using recursive formula 
    for (int i = 2; i <= n; i++)  
    { 
        catalan[i] = 0; 
        for (int j = 0; j < i; j++) 
            catalan[i] += catalan[j]  
                       * catalan[i - j - 1]; 
    } 
  
    // Return last entry 
    return catalan[n]; 
} 
  
// Driver code 
int main() 
{ 
    for (int i = 0; i < 10; i++) 
        cout << catalanDP(i) << " "; 
    return 0; 
}

Output

1 1 2 5 14 42 132 429 1430 4862

Time Complexity: Time complexity of above implementation is O(n2)

Using Binomial Coefficient
We can also use the below formula to find nth Catalan number in O(n) time.

$C_n= rac{1}{n+1}inom{2n}{n}$

We have discussed a O(n) approach to find binomial coefficient nCr.

// C++ program for nth Catalan Number 
#include <iostream> 
using namespace std; 
  
// Returns 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 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 res; 
} 
  
// A 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 2nCn/(n+1) 
    return c / (n + 1); 
} 
  
// Driver code 
int main() 
{ 
    for (int i = 0; i < 10; i++) 
        cout << catalan(i) << " "; 
    return 0; 
}

Output

1 1 2 5 14 42 132 429 1430 4862

Time Complexity: Time complexity of above implementation is O(n).
We can also use below formula to find nth catalan number in O(n) time.

$C_n= rac{(2n)!}{(n+1)!n!}=prod_{k=2}^{n} rac{n+k}{k} for ngeq 0$

Use multi-precision library: In this method, we have used boost multi-precision library, and the motive behind its use is just only to have precision meanwhile finding the large CATALAN%u2019s number and a generalized technique using for loop to calculate Catalan numbers .

For example: N = 5
Initially set cat_=1 then, print cat_ ,
then, iterate from i = 1 to i < 5
for i = 1; cat_ = cat_ * (4*1-2)=1*2=2
cat_ = cat_ / (i+1)=2/2 = 1
For i = 2; cat_ = cat_ * (4*2-2)=1*6=6
cat_ = cat_ / (i+1)=6/3=2
For i = 3 :- cat_ = cat_ * (4*3-2)=2*10=20
cat_ = cat_ / (i+1)=20/4=5
For i = 4 :- cat_ = cat_ * (4*4-2)=5*14=70
cat_ = cat_ / (i+1)=70/5=14

Pseudocode:

a) initially set cat_=1 and print it
b) run a for loop i=1 to i<=n
            cat_ *= (4*i-2)
            cat_ /= (i+1)
            print cat_
c) end loop and exit

  
#include <boost/multiprecision/cpp_int.hpp> 
#include <bits/stdc++.h>
using boost::multiprecision::cpp_int; 
using namespace std; 
  
// Function to print the number 
void catalan(int n) 
{ 
    cpp_int cat_ = 1; 
  
    // For the first number 
    cout << cat_ << " "; // C(0) 
  
    // Iterate till N 
    for (cpp_int i = 1; i < n; i++)  
    { 
        // Calculate the number 
        // and print it 
        cat_ *= (4 * i - 2); 
        cat_ /= (i + 1); 
        cout << cat_ << " "; 
    } 
} 
  
// Driver code 
int main() 
{ 
    int n = 5; 
  
    // Function call 
    catalan(n); 
    return 0; 
}

Output

1 1 2 5 14

Time Complexity: O(n)
Auxiliary Space: O(1)

Name	Views	Likes
C++ Segmented Sieve (Print Primes In a Range)	162	0
C++ Sieve Of Erastosthenes	135	0
C++ Gold Mine Problem	294	0
C++ Merge K Sorted Arrays	116	0
C++ K Centers Problem	239	0
C++ Find Nth Catalan Number	311	0
C++ Inplace Rotate square matrix by 90 degrees	285	0
C++ Find Non Repeating Elements in Array	86	0
C++ Merge Two Binary Trees	120	0
C++ Sum of Numbers From Root To Leaf Paths	88	0
C++ Meta Strings	91	0
C++ Flood Fill Algorithm	401	0
C++ smallest substring with maximum distinct characters	199	0
C++ Smallest window with all characters in string	93	0
C++ Minimum Removal of Characters from string to make its permutation as palindrome	86	0
C++ Minimum characters added at front of string in palindrome conversion	69	0
C++ Number of Bracket Reversals needed to make expression Balanced	72	0
C++ String to Palindrome with Append Function	83	0
C++ WildCard pattern matching	75	0
C++ Anagram substring Search	71	0
C++ Manachars Algorithm	74	0
C++ Search String in Grid	83	0
C++ String Matching(Z Algorithm)	67	0
C++ String Matching(Naive Algorithm)	113	0
C++ String Matching(KMP Algorithm)	140	0
C++ Remove Duplicates From String	110	0
C++ Basics of String Manipulation	84	1
C++ Disjoint Data Structure Cycle Detection	86	0
C++ Problem On Disjoint Data Structures	94	0
C++ Disjoint Data Structures Part3	78	0
Disjoint Data Structures Part2	90	0
Disjoint Data Structures	92	1
C++ Segment Trees	321	2
C++ Trie Cost of Data	290	1
C++ Trie Datastructure	278	1
C++ Greedy Approach Minimum number of coins	525	0
C++ Greedy Approach Maximum height Pyramid	328	1
C++ Greedy Approach String lexicographically largest subsequence	246	0
C++ Greedy Approach Lexicographically largest subsequence	364	0
C++ Greedy Approach Prims MST	398	1
C++ Greedy Approach Krushkals MST	457	1
C++ Greedy Approach N-array maximum sum	333	1
C++ Greedy Approach Policemen Catch Thieves	562	1
C++ Greedy Approach Maximum product Subset	545	1
C++ Greedy Approach Minimum Product Subset	348	1
C++ Greedy Approach Fractional Knapsack	737	1
C++ Greedy Approach-Activity Selection Problem	744	1
C++ Greedy Approach-Egyptian Fractions	639	0
C++ Greedy Approach-Huffman Codes	1030	1
C++ Introduction to Greedy Approach	955	2

Program for nth Catalan Number

More Articles of M Mounika:

Comments

Articles

Quick Links