CODEWITHSUNDEEP
c++cbinomial-coefficients
bhavneet
bhavneet

Reputation: 61

ncr in c (combinations)

I m trying to calculate ncr(combinations) in c using dp. But it is failing with n=70. Can anyone help?

unsigned long long ncr( int n , int r)
{
unsigned long long c[1001];
int i=1; 
c[0]=1;
for(i=1; i<=r; i++)
    c[i]= ((unsigned long long) (c[i-1]) * (unsigned long long)( n-i+1))%(unsigned long long) (1000000007)/ (unsigned long long)(i);
return c[r];
}

basic idea is ncr = ((n-r+1)/r)* nc(r-1)

Upvotes: 0

Views: 1015

Answers (2)

blackmath
blackmath

Reputation: 252

Make the division before the multiplication. a*b/c = (a/c) *b where the second better for overflow which seems your problem.

Upvotes: -1

Basile Starynkevitch
Basile Starynkevitch

Reputation: 1

The intermediate product (unsigned long long) (c[i-1]) * (unsigned long long)( n-i+1) is a very big number, and is overflowing the 64 bits word.

You may want to use bignums. I strongly recommend against developing your own bignum functions (e.g. multiplication and division of bignums), because it is a delicate algorithmic subject (you could still get a PhD about that).

I suggest using some existing bignum library like GMP.

Some languages or implementations (in particular SBCL for Common Lisp) offers native bignum operations. But standard C or C++ don't.

Upvotes: 2

Related Questions