fork download
copy 
  1. // C++ program to find valid paranthesisations of length n
  2. // The majority of code is taken from method 3 of
  3. // https://w...content-available-to-author-only...s.org/program-nth-catalan-number/
  4. #include <bits/stdc++.h>
  5. using namespace std;
  6.  
  7. // Returns value of Binomial Coefficient C(n, k)
  8. unsigned long int binomialCoeff(unsigned int n,
  9.                                 unsigned int k)
  10. {
  11.     unsigned long int res = 1;
  12.  
  13.     // Since C(n, k) = C(n, n-k)
  14.     if (k > n - k)
  15.         k = n - k;
  16.  
  17.     // Calculate value of [n*(n-1)*---*(n-k+1)] / [k*(k-1)*---*1]
  18.     for (int i = 0; i < k; ++i) {
  19.         res *= (n - i);
  20.         res /= (i + 1);
  21.     }
  22.  
  23.     return res;
  24. }
  25.  
  26. // A Binomial coefficient based function to 
  27. // find nth catalan number in O(n) time
  28. unsigned long int catalan(unsigned int n)
  29. {
  30.     // Calculate value of 2nCn
  31.     unsigned long int c = binomialCoeff(2 * n, n);
  32.  
  33.     // return 2nCn/(n+1)
  34.     return c / (n + 1);
  35. }
  36.  
  37. // Function to find possible ways to put balanced
  38. // parenthesis in an expression of length n
  39. unsigned long int findWays(unsigned n)
  40. {
  41.     // If n is odd, not possible to 
  42.     // create any valid parentheses
  43.     if (n & 1)
  44.         return 0;
  45.  
  46.     // Otherwise return n/2'th Catalan Number
  47.     return catalan(n / 2);
  48. }
  49.  
  50. // Driver program to test above functions
  51. int main()
  52. {
  53.     int n = 30000;
  54.     cout << "Total possible expressions of length "
  55.          << n << " is " << findWays(30000);
  56.     return 0;
  57. }
Success #stdin #stdout 0.01s 5300KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Total possible expressions of length 30000 is 2687542030
https://ideone.com/fmaH7J
language:
C++14 (gcc 8.3)
created:
34 days ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!