{"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 &#8211; Program for nth Catalan Number"},"content":{"rendered":"<p>Catalan numbers are a sequence of natural numbers that occurs in many interesting counting problems like following.<span id=\"more-129065\"><\/span><\/p>\n<p><strong>1)<\/strong> Count the number of expressions containing n pairs of parentheses which are correctly matched. For n = 3, possible expressions are ((())), ()(()), ()()(), (())(), (()()).<\/p>\n<p><strong>2)<\/strong> Count the number of possible Binary Search Trees with n keys (See <a href=\"http:\/\/www.geeksforgeeks.org\/g-fact-18\/\" target=\"_blank\" rel=\"noopener noreferrer\">this<\/a>)<\/p>\n<p><strong>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<p>The first few Catalan numbers for n = 0, 1, 2, 3, \u2026 are <strong>1, 1, 2, 5, 14, 42, 132, 429, 1430, 4862, \u2026<\/strong><\/p>\n<p><strong>Recursive Solution<\/strong><br \/>\nCatalan numbers satisfy the following recursive formula.<\/p>\n<p><img decoding=\"async\" class=\"aligncenter size-full wp-image-26122\" src=\"https:\/\/www.wikitechy.com\/technology\/wp-content\/uploads\/2017\/05\/catalan.png\" alt=\"catalan\" width=\"375\" height=\"19\" srcset=\"https:\/\/www.wikitechy.com\/technology\/wp-content\/uploads\/2017\/05\/catalan.png 375w, https:\/\/www.wikitechy.com\/technology\/wp-content\/uploads\/2017\/05\/catalan-300x15.png 300w\" sizes=\"(max-width: 375px) 100vw, 375px\" \/><\/p>\n<p>Following is the implementation of above recursive formula.<\/p>\n[pastacode lang=\u201dcpp\u201d manual=\u201d%23include%3Ciostream%3E%0Ausing%20namespace%20std%3B%0A%20%0A%2F%2F%20A%20recursive%20function%20to%20find%20nth%20catalan%20number%0Aunsigned%20long%20int%20catalan(unsigned%20int%20n)%0A%7B%0A%20%20%20%20%2F%2F%20Base%20case%0A%20%20%20%20if%20(n%20%3C%3D%201)%20return%201%3B%0A%20%0A%20%20%20%20%2F%2F%20catalan(n)%20is%20sum%20of%20catalan(i)*catalan(n-i-1)%0A%20%20%20%20unsigned%20long%20int%20res%20%3D%200%3B%0A%20%20%20%20for%20(int%20i%3D0%3B%20i%3Cn%3B%20i%2B%2B)%0A%20%20%20%20%20%20%20%20res%20%2B%3D%20catalan(i)*catalan(n-i-1)%3B%0A%20%0A%20%20%20%20return%20res%3B%0A%7D%0A%20%0A%2F%2F%20Driver%20program%20to%20test%20above%20function%0Aint%20main()%0A%7B%0A%20%20%20%20for%20(int%20i%3D0%3B%20i%3C10%3B%20i%2B%2B)%0A%20%20%20%20%20%20%20%20cout%20%3C%3C%20catalan(i)%20%3C%3C%20%22%20%22%3B%0A%20%20%20%20return%200%3B%0A%7D\u201d message=\u201dC++\u201d highlight=\u201d\u201d provider=\u201dmanual\u201d\/]\n<p>\u00a0<\/p>\n<p><strong>Output :<\/strong><\/p>\n<pre>1 1 2 5 14 42 132 429 1430 4862<\/pre>\n<p>The value of nth catalan number is exponential that makes the time complexity exponential.<\/p>\n[ad type=\u201dbanner\u201d]\n<p><strong>Dynamic Programming Solution<\/strong><br \/>\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[pastacode lang=\u201dcpp\u201d manual=\u201d%23include%3Ciostream%3E%0Ausing%20namespace%20std%3B%0A%20%0A%2F%2F%20A%20dynamic%20programming%20based%20function%20to%20find%20nth%0A%2F%2F%20Catalan%20number%0Aunsigned%20long%20int%20catalanDP(unsigned%20int%20n)%0A%7B%0A%20%20%20%20%2F%2F%20Table%20to%20store%20results%20of%20subproblems%0A%20%20%20%20unsigned%20long%20int%20catalan%5Bn%2B1%5D%3B%0A%20%0A%20%20%20%20%2F%2F%20Initialize%20first%20two%20values%20in%20table%0A%20%20%20%20catalan%5B0%5D%20%3D%20catalan%5B1%5D%20%3D%201%3B%0A%20%0A%20%20%20%20%2F%2F%20Fill%20entries%20in%20catalan%5B%5D%20using%20recursive%20formula%0A%20%20%20%20for%20(int%20i%3D2%3B%20i%3C%3Dn%3B%20i%2B%2B)%0A%20%20%20%20%7B%0A%20%20%20%20%20%20%20%20catalan%5Bi%5D%20%3D%200%3B%0A%20%20%20%20%20%20%20%20for%20(int%20j%3D0%3B%20j%3Ci%3B%20j%2B%2B)%0A%20%20%20%20%20%20%20%20%20%20%20%20catalan%5Bi%5D%20%2B%3D%20catalan%5Bj%5D%20*%20catalan%5Bi-j-1%5D%3B%0A%20%20%20%20%7D%0A%20%0A%20%20%20%20%2F%2F%20Return%20last%20entry%0A%20%20%20%20return%20catalan%5Bn%5D%3B%0A%7D%0A%20%0A%2F%2F%20Driver%20program%20to%20test%20above%20function%0Aint%20main()%0A%7B%0A%20%20%20%20for%20(int%20i%20%3D%200%3B%20i%20%3C%2010%3B%20i%2B%2B)%0A%20%20%20%20%20%20%20%20cout%20%3C%3C%20catalanDP(i)%20%3C%3C%20%22%20%22%3B%0A%20%20%20%20return%200%3B%0A%7D%0A\u201d message=\u201dC++ Program \u201d highlight=\u201d\u201d provider=\u201dmanual\u201d\/]\n<p><strong>Output:<\/strong><\/p>\n<pre>1 1 2 5 14 42 132 429 1430 4862<\/pre>\n<p>Time Complexity: Time complexity of above implementation is O(n<sup>2<\/sup>)<\/p>\n[ad type=\u201dbanner\u201d]\n<p><strong>Using Binomial Coefficient <\/strong><br \/>\nWe can also use the below formula to find nth catalan number in O(n) time.<\/p>\n[pastacode lang=\u201dcpp\u201d manual=\u201d%23include%3Ciostream%3E%0Ausing%20namespace%20std%3B%0A%20%0A%2F%2F%20Returns%20value%20of%20Binomial%20Coefficient%20C(n%2C%20k)%0Aunsigned%20long%20int%20binomialCoeff(unsigned%20int%20n%2C%20unsigned%20int%20k)%0A%7B%0A%20%20%20%20unsigned%20long%20int%20res%20%3D%201%3B%0A%20%0A%20%20%20%20%2F%2F%20Since%20C(n%2C%20k)%20%3D%20C(n%2C%20n-k)%0A%20%20%20%20if%20(k%20%3E%20n%20-%20k)%0A%20%20%20%20%20%20%20%20k%20%3D%20n%20-%20k%3B%0A%20%0A%20%20%20%20%2F%2F%20Calculate%20value%20of%20%5Bn*(n-1)*\u2014*(n-k%2B1)%5D%20%2F%20%5Bk*(k-1)*\u2014*1%5D%0A%20%20%20%20for%20(int%20i%20%3D%200%3B%20i%20%3C%20k%3B%20%2B%2Bi)%0A%20%20%20%20%7B%0A%20%20%20%20%20%20%20%20res%20*%3D%20(n%20-%20i)%3B%0A%20%20%20%20%20%20%20%20res%20%2F%3D%20(i%20%2B%201)%3B%0A%20%20%20%20%7D%0A%20%0A%20%20%20%20return%20res%3B%0A%7D%0A%20%0A%2F%2F%20A%20Binomial%20coefficient%20based%20function%20to%20find%20nth%20catalan%0A%2F%2F%20number%20in%20O(n)%20time%0Aunsigned%20long%20int%20catalan(unsigned%20int%20n)%0A%7B%0A%20%20%20%20%2F%2F%20Calculate%20value%20of%202nCn%0A%20%20%20%20unsigned%20long%20int%20c%20%3D%20binomialCoeff(2*n%2C%20n)%3B%0A%20%0A%20%20%20%20%2F%2F%20return%202nCn%2F(n%2B1)%0A%20%20%20%20return%20c%2F(n%2B1)%3B%0A%7D%0A%20%0A%2F%2F%20Driver%20program%20to%20test%20above%20functions%0Aint%20main()%0A%7B%0A%20%20%20%20for%20(int%20i%20%3D%200%3B%20i%20%3C%2010%3B%20i%2B%2B)%0A%20%20%20%20%20%20%20%20cout%20%3C%3C%20catalan(i)%20%3C%3C%20%22%20%22%3B%0A%20%20%20%20return%200%3B%0A%7D\u201d message=\u201dC++ Program\u201d highlight=\u201d\u201d provider=\u201dmanual\u201d\/]\n<p>Output:<\/p>\n<pre>1 1 2 5 14 42 132 429 1430 4862<\/pre>\n<p>Time Complexity: Time complexity of above implementation is O(n).<\/p>\n<p>We can also use below formula to find nth catalan number in O(n) time.<\/p>\n[ad type=\u201dbanner\u201d]\n<p>\u00a0<\/p>\n","protected":false},"excerpt":{"rendered":"<p>C++ Programming Program for nth Catalan Number &#8211; Mathematical Algorithms &#8211; 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}]}}