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 :-
link text

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:

binomial coefficient formula

So you do not need multiplication/deletion, just addition :wink:

2 Likes

thank you it helped me :slight_smile:

welcome :slight_smile: