Calculate Value Of N Choose K

Answer :

Here is my version, which works purely in integers (the division by k always produces an integer quotient) and is fast at O(k):

function choose(n, k)     if k == 0 return 1     return (n * choose(n - 1, k - 1)) / k 

I wrote it recursively because it's so simple and pretty, but you could transform it to an iterative solution if you like.

You could use the Multiplicative formula for this:

http://en.wikipedia.org/wiki/Binomial_coefficient#Multiplicative_formula

Probably the easiest way to compute binomial coefficients (n choose k) without overflowing is to use Pascal's triangle. No fractions or multiplications are necessary. (n choose k). The nth row and kth entry of Pascal's triangle gives the value.

Take a look at this page. This is an O(n^2) operation with only addition, which you can solve with dynamic programming. It's going to be lightning fast for any number that can fit in a 64-bit integer.