CODEWITHSUNDEEP
javaalgorithm
Jainendra
Jainendra

Reputation: 25153

Most efficient way to calculate nCr modulo 142857

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?

Upvotes: 3

Views: 1252

Answers (3)

maaartinus
maaartinus

Reputation: 46492

As your number is no prime, this answer doesn't apply. But you could easily decompose 142857 into primes, compute the corresponding moduli, and use the Chinese Remainder Theorem to get your result. This may or may not make sense for numbers you're working with.

In any case you must avoid double, unless you can be sure that all your intermediate results can be represented exactly with only 53 bits (otherwise you lose precision and get a non-sense out).

Upvotes: 1

user1952500
user1952500

Reputation: 6781

You already have most of the answer in the function that you mention. If n is fixed and r is variable, you can use nCr = nC(r-1) * (n - r + 1) / r. So you can use a table for nCr and build it incrementally (unlike what the other answer mentions where precomputation is not incremental).

So your new function can be made recursive with a table being passed.

Upvotes: 0

Adam Stelmaszczyk
Adam Stelmaszczyk

Reputation: 19847

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.

Upvotes: 1

Related Questions