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.