Solution for large value of n?

#1


This is my code , even though it has passed all the given test cases but it will not pass for large n , like n = 100. Could you give a c++ based solution , possibly using boost library ?

#2

there is a simple approach to find catalan number:
try to implement the recursive definition of catalan number as dynamic programming solution(means memoisation is imp) which is,
t(n) = sum[i=0 to n-1]{t(i) multiply t(n-i-1}
t(n) is nth catalan number.

you can do it in O(n^2) which means it will work for the value around 10000 for n.
and the solution is:
unsigned long int catalanDP(unsigned int n)
{
unsigned long int catalan[n+1];
catalan[0] = catalan[1] = 1;
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 catalan[n];
}

but if you need to find out catalan number for n larger than 10000, you need a o(n) solution.
Hint: try to solve that mathematical expression in more simpler form.

thanks

#3

I hope I’ve cleared your doubt. I ask you to please rate your experience here
Your feedback is very important. It helps us improve our platform and hence provide you
the learning experience you deserve.

On the off chance, you still have some questions or not find the answers satisfactory, you may reopen
the doubt.