Help Me to Debug

#1

Print nth Catalan Number. The first few Catalan numbers for n = 0, 1, 2, 3, … are 1, 1, 2, 5, 14,… .

Input Format
One integer n

Constraints
1 <= N <= 100

Output Format
Print the catalan number at position N.

Sample Input
10
Sample Output
16796

#include<bits/stdc++.h>
#include
#define l long long int
using namespace std;

l catalan(l n){

if(n == 0 || n == 1){
	return 1;
}
n = (double) n;
double ans = 1;
for(double k=2;k<=n;k++){

// cout<<"ans "<<ans<<endl;
ans = (ans * ((n+k)/k));
}
return ans;
}

int main(){
l n;
cin>>n;
cout<<catalan(n)<<endl;
return 0;
}

#2

Hello @amangoel987357,

Rather using double, use unsigned long long int.
Reason:
Unsigned long variables are extended size variables for number storage and stores only positive numbers and hence can accommodate longer ranges of values than long long.

Hope, this would help.
Give a like if you are satisfied.

#3

Hey Why you don’t you try that out first before telling it to me. It Still not working.

#4

Hello @amangoel987357,

Thanks for the advice.
BTW, as the constraint for this question is:
1 <= N <= 100

So, for bigger value of N the catalan is/can be greater than the range of double and long long it.
Thus, I suggested that change.

The code you have written would work perfectly for smaller value of N But fail for larger values.
Reason:
It includes division of numbers and the result can be a decimal value also.
But, double cannot store a bigger number as required by the question.
Example:
N=100
Catalan number: 7159379471982673992

So, I would suggest you to use a different manner to solve this solve which do not requires division so that you can use unsigned log long int to accommodate such a big number.

For reference, you can click on this this link.

Let me know if you face any issue.

#5

// Now tell me what is the problem with this approach i am going to divide two integers at the end and the //answer is always going to be an integer
// formula for catalan is (2n!) / ((n+1)!* (n!)) which can be simplified as (n+2)*(n+3) … *(2n) / n!

#include<bits/stdc++.h>
#include
#define l unsigned long long int
using namespace std;

l catalan(l n){

if(n == 0 || n == 1){
	return 1;
}
l ans=1;
for(l i=n+2;i<=2*n;i++){
	ans *= i;
}

l ans1 = 1;
for(l i=1;i<=n;i++){
	ans1 = ans1* i;
}

return (l)(ans/ans1);

}

int main(){
l n;
cin>>n;

cout<<catalan(n)<<endl;
return 0;

}

#6

Hello @S18ML0016,

There is surely a problem with this code:
The result of MULTIPLICATION is the problem.

The first for loop that you have used will result in the values that would be out of the range of unsigned long long int.

You can see the following code where i have printed the result of multiplication in each iteration:

You will see the drop in the value of ans after i=35.
While it should have been increased with each iteration.
Reason:
The result of the product being too large, the value of ans is revolving within the range of unsigned long long int.

NOTE:
It is failing for N=20 while the constraint given in the question is 1<=N<=100.

Solution:
image
where T(n) is the nth Catalan number.
Logic:
We can observe that the above recursive implementation does a lot of repeated work (we can the same by drawing the recursion tree). Since there are overlapping subproblems, we can use dynamic programming for this. Following is a Dynamic programming based implementation.

As you might have not studied the DP yet.
I’ll give you a brief idea of it:

When you use recursive code, you might call the same function(which is recursion) with same parameters multiple times.
Example: finding nth Fibonacci number.
Formula: fib(n)=fib(n-1)+fib(n-2)
So, to find fib of n you need to call fib of n-1 and n-2.
But, when you have to find fib of n-1, you will call fib(n-2) and fib(n-3).

But, as you have already computed the value of fib(n-2) while calling for fib(n). So, there is no need to repeat the same process again, as it will be a chain of the recursive call.
This is called overlapping subproblems.
Thus, to avoid this repetition of same chain of process, we will store the results and if the same call is made again i.e. f(n-2) in case of f(n-1), we will just read the stored value.
This is called memorization.

Let me know if you face any difficulty in understanding the code.

#7

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.