nCr

JavaView on GFG

Intuition

Compute nCr (binomial coefficient) mod p. Pascal triangle DP or Fermat little theorem with modular inverse.

Algorithm

1Pascal: dp[i][j] = dp[i-1][j-1] + dp[i-1][j] mod p.
2For large n: precompute factorials and modular inverses. nCr = n! * modinv(r!) * modinv((n-r)!) mod p.

Common Pitfalls

•Pascal for small n. Modular inverse for large n (when p is prime use Fermat: a^(p-2) mod p).

nCr.java

Java

// Approach: DP Pascal's triangle or multiplicative formula with modular inverse (for large n).
// Time: O(n*r) or O(r) Space: O(n*r) or O(r)
package solutions.nCr;

class Solution {
    public int nCr(int n, int r) {
        if (r > n)
            return 0;

        long res = 1;
        for (int i = 0; i < r; i++) {
            res = res * (n - i);
            res = res / (i + 1);
        }

        return (int) res;
    }
}

Was this solution helpful?