Binomal coefficient

Can someone give me efficient algorithm for calculating binomial coefficient? Thanks in advance, Aleksandar. ;)

You could find all numbers you multiply in numerator( 1 .. n ) and all numbers you multiply in denominator ( 1 .. k , 1 .. n - k ).

Now you have two sets of numbers and you delete ones that are in both of them.

Edit: and then you multiply all numbers in each set ( not STL set, but set in math ) and divide the products.

Thanks. I found a recursive solution that works really fast. ;)

Share! :)

Here you go.

Function Bin_Coeff(n, k:LongInt):LongInt;
Begin
If ( ( k = 0 ) Or ( k = n ) ) Then Bin_Coeff:=1
Else Bin_Coeff:=Bin_Coeff(n - 1, k - 1 ) + Bin_Coeff(n - 1, k );
End;

Yeah, that formula is nice, but are u sure it's fast, u're going 2^n there....as far as I see...

I'm not sure, but I didn't get TLE on z-Attack. :( Maybe it's not good for very big numbers.

You could speed it up by memoizing. However if you want to get faster, just use combinatorics. nCr = n!/[r!(n-r)!] <-- (this simplifies to what tgudlek said)

I belive he wants to calculate that but with avoiding overflow, if possible :)

frank44 said: "You could speed it up by memoizing."

Yes, I think this is the most efficient way to calculate it without overflow risks...

#define MAX 20
long long memo[MAX][MAX];
//remember to initialize all memo[i][j] with the value -1
long long bin_coef(long long n, long long k) {
if(memo[n][k] != -1) return memo[n][k];
if(k == 0 || k == n) return (memo[n][k] = 1);
return (memo[n][k] = bin_coef(n-1, k-1) + bin_coef(n-1,k));
}

iteratively:

C[0][0] = 0;
for( int i = 1; i < MAX; ++i ) {
	C[i][0] = 1;
	for( int j = 1; j <= i; ++j )
		C[i][j] = C[ i - 1 ][ j - 1 ] + C[ i - 1 ][j];
}