UVA 369 - Combinations

Problem link

I like to implement n choose k in a functional language like so:

n `choose` k
  | k > n           = undefined
  | k == 0          = 1
  | k > (n `div` 2) = n `choose` (n-k)
  | otherwise       = n * ((n-1) `choose` (k-1)) `div` k
Or in an imperative language like so:

f(n, k) {
  if(k >  n)
    throw some_exception;
  if(k == 0)
    return 1;
  if(k > n/2)
    return f(n,n-k);
  return n * f(n-1,k-1) / k;
}

It is pretty easy to see that both implementations run in O(k)O(k) time and avoids overflow errors of fixed precision numbers much better than calculating.n!/(n-k)!

reference

A solution in C++




A solution in java