C++ function to calculate factorial returns negative value

Question

I've written a C++ function to calculate factorial and used it to calculate ²²C₁₁ (Combination). I have declared a variable ans and set it to 0. I tried to calculate

22C11 = fact(2*n)/(fact(n)*fact(n))

where i sent n as 11. For some reason, i'm getting a negative value stored in answer. How can i fix this?

long int fact(long int n) {
    if(n==1||n==0)
        return 1;
    long int x=1;
    if(n>1)
    x=n*fact(n-1);
    return x;
}

The following lines are included in the main function:

long int ans=0;
    ans=ans+(fact(2*n)/(fact(n)*fact(n)));
cout<<ans;

The answer i'm getting is -784 The correct answer should be 705432

NOTE: This function is working perfectly fine for n<=10. I have tried long long int instead of long int but it still isn't working.

Answer 1

It is unwise to actually calculate factorials - they grow extremely fast. Generally, with combinatorial formulae it's a good idea to look for a way to re-order operations to keep intermediate results somewhat constrained.

For example, let's look at (2*n)!/(n!*n!). It can be rewritten as ((n+1)*(n+2)*...*(2*n)) / (1*2*...*n) == (n+1)/1 * (n+2)/2 * (n+3)/3 ... * (2*n)/n. By interleaving multiplication and division, the rate of growth of intermediate result is reduced.

So, something like this:

int f(int n) {
  int ret = 1;
  for (int i = 1; i <= n; ++i) {
    ret *= (n + i);
    ret /= i;
  }
  return ret;
}

Demo