Most efficient way to calculate nCr modulo 142857

Question

I want to calculate nCr modulo 142857. Following is my code in Java:

private static int nCr2(int n, int r) {
    if (n == r || r == 0) {
        return 1;
    }
    double l = 1;
    if (n - r < r) {
        r = n - r;
    }
    for (int i = 0; i < r; i++) {
        l *= (n - i);
        l /= (i + 1);
    }
    return (int) (l % 142857);
}

This gives nCr in O(r) time. I want an algorithm to get the result in less time than this. Is there such an algorithm?

Answer 1

You can precompute results for given n and r pairs and hard-code them in the table int t[][].

Later, during run-time, when you need nCr(n, r), you just make a look-up to this table: t[n][r].

This is O(1) during run-time.