{"id":26118,"date":"2017-10-26T19:59:19","date_gmt":"2017-10-26T14:29:19","guid":{"rendered":"https:\/\/www.wikitechy.com\/technology\/?p=26118"},"modified":"2017-10-26T19:59:19","modified_gmt":"2017-10-26T14:29:19","slug":"c-programming-program-nth-catalan-number","status":"publish","type":"post","link":"https:\/\/www.wikitechy.com\/technology\/c-programming-program-nth-catalan-number\/","title":{"rendered":"C++ Programming – Program for nth Catalan Number"},"content":{"rendered":"

Catalan numbers are a sequence of natural numbers that occurs in many interesting counting problems like following.<\/span><\/p>\n

1)<\/strong> Count the number of expressions containing n pairs of parentheses which are correctly matched. For n = 3, possible expressions are ((())), ()(()), ()()(), (())(), (()()).<\/p>\n

2)<\/strong> Count the number of possible Binary Search Trees with n keys (See this<\/a>)<\/p>\n

3)<\/strong> 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.<\/p>\n

The first few Catalan numbers for n = 0, 1, 2, 3, \u2026 are 1, 1, 2, 5, 14, 42, 132, 429, 1430, 4862, \u2026<\/strong><\/p>\n

Recursive Solution<\/strong>
\nCatalan numbers satisfy the following recursive formula.<\/p>\n

\"catalan\"<\/p>\n

Following is the implementation of above recursive formula.<\/p>\n

C++<\/span> <\/div> 
#include<iostream>using namespace std; \/\/ A recursive function to find nth catalan numberunsigned 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 program to test above functionint main(){    for (int i=0; i<10; i++)        cout << catalan(i) << " ";    return 0;}<\/code><\/pre> <\/div>\n
 <\/p>\n
Output :<\/strong><\/p>\n
1 1 2 5 14 42 132 429 1430 4862<\/pre>\n
The value of nth catalan number is exponential that makes the time complexity exponential.<\/p>\n[ad type=”banner”]\n
Dynamic Programming Solution<\/strong>
\nWe 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 in C++.<\/p>\n
 
 C++ Program <\/span> <\/div> 
#include<iostream>using namespace std; \/\/ A dynamic programming based function to find nth\/\/ Catalan numberunsigned 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 program to test above functionint main(){    for (int i = 0; i < 10; i++)        cout << catalanDP(i) << " ";    return 0;}<\/code><\/pre> <\/div>\n
Output:<\/strong><\/p>\n
1 1 2 5 14 42 132 429 1430 4862<\/pre>\n
Time Complexity: Time complexity of above implementation is O(n2<\/sup>)<\/p>\n[ad type=”banner”]\n
Using Binomial Coefficient <\/strong>
\nWe can also use the below formula to find nth catalan number in O(n) time.<\/p>\n
 
 C++ Program<\/span> <\/div> 
#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) timeunsigned 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 program to test above functionsint main(){    for (int i = 0; i < 10; i++)        cout << catalan(i) << " ";    return 0;}<\/code><\/pre> <\/div>\n
Output:<\/p>\n
1 1 2 5 14 42 132 429 1430 4862<\/pre>\n
Time Complexity: Time complexity of above implementation is O(n).<\/p>\n
We can also use below formula to find nth catalan number in O(n) time.<\/p>\n[ad type=”banner”]\n
 <\/p>\n","protected":false},"excerpt":{"rendered":"
C++ Programming Program for nth Catalan Number – Mathematical Algorithms – Catalan numbers are a sequence of natural numbers that occurs in many interesting<\/p>\n","protected":false},"author":2,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[69969,83515,1,74058],"tags":[77217,77233,77126,77211,77225,77241,77206,77216,77224,77227,77223,77198,77240,77232,77215,77222,77213,77199,77235,77228,77209,77237,77219,77234,77230,77201,77218,77208,77214,77243,77229,77226,77238,77221,77205,77204,77203,77242,77197,77210,77236,77220,77200,73686,70398,77239,77207,77212,77231,77202],"class_list":["post-26118","post","type-post","status-publish","format-standard","hentry","category-algorithm","category-c-programming-3","category-coding","category-mathematical-algorithms","tag-0-1-1-2","tag-1-2-5","tag-1-2-5-14","tag-1-2-of-5","tag-1-in","tag-1-number","tag-14-42","tag-2-5-1","tag-5-14","tag-armstrong-number-wiki","tag-c-n","tag-catalan","tag-catalan-meaning","tag-catalan-numbers","tag-catalan-series","tag-catalana","tag-cn-formula","tag-cn-meaning","tag-convex-hexagon","tag-convex-octagon","tag-de-catalon","tag-define-admissible","tag-define-convex-polygon","tag-define-rigged","tag-discrete-mathematics-recurrence-relations-and-generating-functions","tag-expression-number","tag-factors-of-42-in-pairs","tag-fine-number","tag-handshake-problem-formula","tag-hasse-diagram-example-problems","tag-i-2-pill","tag-mountain-range-definition","tag-narcissistic-number","tag-natural-numbers-wiki","tag-number","tag-number-2","tag-number-expression","tag-number-of-diagonals-formula","tag-number-relation-problems-with-solutions","tag-pair-of-parentheses","tag-parenthesis-example","tag-prime-factors-of-132","tag-q-maths","tag-recursion-in-python","tag-recursive-formula","tag-simple-tree","tag-square-root-of-132","tag-squared-5","tag-well-formed-formula-in-discrete-mathematics","tag-xiv-in-numbers"],"_links":{"self":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/posts\/26118","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/users\/2"}],"replies":[{"embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/comments?post=26118"}],"version-history":[{"count":0,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/posts\/26118\/revisions"}],"wp:attachment":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/media?parent=26118"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/categories?post=26118"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/tags?post=26118"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}