CareerCup

Just compute the coefficient by doing 1* (N/1) * (N-1)/2 * (N-2)/3 *...

At each step, the answer will be an integer and no rounding etc will happen.

long capped_binomial(uint n, uint k) {

long answer = 1;
long r = 0;
while (r < k) {
    // there might be overflow issues here. Consider those too.
   // Just the check against 1 billion might not be sufficient.
    answer = answer*(N-r)/(r+1);
    if (answer > 1000000000) return -1;
    r++;
}

}

#include <iostream>
using namespace std;

int memoarr[50][50];

int binomial(int n, int k)
{
    if (k == 0) {
        memoarr[n][0] = 1;
        return 1;
    } else if (n == k) {
        memoarr[n][k] = 1;
        return 1;
    } else if (memoarr[n][k] > 0) {
        return memoarr[n][k];
    } else {
        int lhs = binomial(n-1, k-1), rhs = binomial(n-1, k);
        if (lhs == -1 || rhs == -1)
            return -1;
        memoarr[n][k] = lhs + rhs;
        if (memoarr[n][k] > 1000000000) {
            return -1;
        }
    }
    return memoarr[n][k];
}

int main(int args, char **argv)
{
    cout << binomial(10,6) << endl;
}

Alternate way is to just compute multiplication of n * (n-1) * (n-2).... (n - max(n-k, k) +1), and factorial of (min(n-k, k))! and do the division of numerator and denimonator. I was not sure which one was expected to be the solution.
Since they allow some space complexity which was in terms of N*K, I assume that what I have posted is right.
Additionally since their constraint is that if "n choose k" is > 1 billion, return -1, they anyways don't expect memoization array to be greater than 40 x 40.

In O(k) space and O(k^2) time (k^2 = O(n * min(k, n - k)).
Assume k < n /.2, i.e., min(k, n - k) == k is true

The goal is to do the integer division first to make sure we can have the largest possible numbers without throwing an overflow.

public int nChoosek(int n, k) {
// Do division first
// We are evaluating N * (N - 1) * ... * (N - k + 1) / (k * (k - 1) * .... * 1).
// Numerator values (N, N - 1, ...)
int[] C = new int[k];
for (int i = 0; i < k; i++)
C[i] = N - i;
for (int i = 0; i < k; i++) {
	// i + 1 is a denumerator value, i.e., i + 1 = 1, 2, ..., k
    for (int j = 0; j < k; j++) {	
       // Find an element from numerator which divides (i + 1)
        if (C[j] % (i + 1) == 0) {
           C[j] = C[j] / (i + 1);
           break;
        }
    }
}

// Now do product
int result = 1;
for (int i = 0; i < k; i++) {
 if (i < (k - 1)) {
  if (result > (1000000 / C[i + 1]))
 	return -1;  // This would be an overflow anyway
}
  result *= C[i];
}
return result;
}

Best way is to use recursion and memo calls

f(n,k) = f(n-1, k) + f(n-1, k-1)
f(0, x) = 0

CV: spoj.com/SPOJ/users/mogers/

@Anonymous, Miguel said memo the calls so it is linear not exponential.