 # Combination

Hello all,
I want to calculate combination of two numbers n and r i.e nCr. I know that how to store factorial of numbers greater than 20 in array but I don’t know how to use that array in further calculations.Please help.

@rjohari you are wrong.

This will be very clumpsy task to do that way ,
usually the problem involved calculating nCr in competitive coding will mention the line that
"nCr will fit in long long int " or you have to find ( nCr mod m .)
but if you do it by calculating factorial it will definitely exceed the limits of long long int .
here is the correct approach :-

also i am pasting the code for calculating nCr mod m :-

`````` long modPow(long a, long x, long p) {
//calculates a^x mod p in logarithmic time.
long res = 1;
while(x > 0) {
if( x % 2 != 0) {
res = (res * a) % p;
}
a = (a * a) % p;
x /= 2;
}
return res;
``````

}

`````` long modInverse(long a, long p) {
//calculates the modular multiplicative of a mod m.
//(assuming p is prime).
return modPow(a, p-2, p);
``````

}

``````  long modBinomial(long n, long k, long p) {

// calculates C(n,k) mod p (assuming p is prime).

long numerator = 1; // n * (n-1) * ... * (n-k+1)
for (int i=0; i<k; i++) {
numerator = (numerator * (n-i) ) % p;
}

long denominator = 1; // k!
for (int i=1; i<=k; i++) {
denominator = (denominator * i) % p;
}

// numerator / denominator mod p.
return ( numerator* modInverse(denominator,p) ) % p;
``````

}

1 Like

There is easier way how to do it, quite easy to implement with big numbers also.

You know Pascal’s triangle, right?

We know that: So you do not need multiplication/deletion, just addition 2 Likes

thank you it helped me welcome 