C++ Find Nth Catalan Number














































C++ Find Nth Catalan Number



Program for 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)



More Articles of M Mounika:

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

Comments